堆 - 最小和最大

堆 - 最小堆

堆是优先级列表的更高效版本。考虑到 Priority Queue Sorted 和 Unsorted 的插入和移除方法，Unsorted 的插入成本为 O(1)，移除成本为 O(n)，而 Sorted 的插入成本为 O(n)，移除成本为 O(1)。

	sorted	unsorted
insert	O(n)	O(1)
remove	O(1)	O(n)

堆是由数组构建的，但它的表示是一棵二叉树，优先级最高的元素位于顶部，即根。从上到下、从右到左都塞满了，没有一个孩子漏掉！

？

但是，有可能构建由最高键值定义的最高优先级的数据结构。在这种情况下，我们有最大堆，我们稍后会看到。

最小堆

要成为有效的堆，所有子元素的优先级必须低于或等于其父元素。此外，它必须是完整的，不能缺少子元素，否则数组将有空格。

？

执行此定义的更正式方法是，如果二叉树的级别 0、1、2、···h − 1 具有最大可能元素并且分配了级别 h 中存在的元素，则二叉树是完整的尽可能靠左。

如上所述，堆由数组组成（以绿色表示），但可以将其视为树结构，如下图所示。

组装Heap有两种方法，第一个元素位于位置0，或者不位于位置0，在本文中我们将看到两种情况之间的区别。顶部的元素总是有它们的子元素，通常称为底部的元素，要发现这些子元素，在索引为 0 的情况下，您可以使用以下计算获得此信息：

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

如果使用不填0的版本，只需减少总和即可，即1-1=0，在父情况下是index / 2。

插入

它总是添加在末尾，您唯一应该关心的是检查子元素是否具有比父元素更低的键，为此目的会执行冒泡，即插入元素的键为和父亲相比，必要时改变。

更详细地说，将元素放置在树的最后一个空白空间中，因为您需要将其键与父元素的键进行比较，所以我们需要计算父元素的索引以访问其键。要找出父亲，请使用提到的计算：

parent = (indexDoFilho -1)/2

为此，indexDoFilho丢失了：为了获得它，我们将一个变量作为当前索引，因为我们在插入中是最后一个添加，当前索引是最后一个，是：

currentIndex = size-1

现在有了当前索引，调用 Parent 并找出正在插入的元素的父元素。我们需要这个新元素的父元素，因为为了正确组织树，必须将该元素与其父元素进行比较，如果其键较小，则它们必须交换位置。

只要当前索引大于0（为了避免拾取不可用的索引）并且当前索引小于父级索引，如果这个条件成立，则需要与父级交换该元素以保证最小堆的所有权，然后发生交换，然后当前索引接收父级的索引，然后将父级的父级（KKKKK）取为 。 Swap 是一种使用正常交换值的结构的方法。

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

有关联：

parent = (indexDoFilho -1)/2

交换是交换值的正常方法：

currentIndex = size-1

如果当前（子）元素的值小于父元素的值，则表明违反了最小堆属性。在最小堆中，父堆必须始终小于或等于子堆。 当不满足此条件时，子级必须与父级交换位置，以便较小的值继续在堆中“爬升”，直到找到正确的位置，在该位置将维护属性。

消除

删除索引 0 的元素，但树不再完整！要解决这个问题，请将数组的最后一个元素拉到开头，即添加的最后一个元素位于树的顶部。之后，再次检查，但现在是从上到下。换句话说，现在是父母和孩子比较的时候了！ （下沉）
sinkDown() 方法将元素在堆中向下移动（或“下沉”），直到它位于正确的位置，其中它的值小于或等于其子元素的值（如果它位于有子元素的位置） .
在sinkDown中，有一个变量用于存储从根开始的最低键的元素的索引，另一个变量用于存储当前索引。然后，循环将持续到当前元素的索引等于具有最低键的元素的索引。在循环内部，获取当前的子级，并查看子级是否在数组范围内，如果子级索引小于最小索引，则更新最小值。

public void insert(K key, V value) { //o(log n)
    if (isFull()){
        throw new RuntimeException("full");
    }
    //adc a entry na ultima posição do vetor
    heap[size++]=new PriorityEntry(key, value);
    //guarda o index que esse novo elemento tá
    int currentIndex = size-1;
    //chama o método parent pra calcular quem é o pai do novo elemento
    int parent = parent(currentIndex);
    //percorre enquanto o index nao for o 0 e o index ser 
    while (currentIndex>0 && compare(currentIndex, parent)<0){
        swap(currentIndex, parent);
        currentIndex = parent;
        parent = parent(currentIndex);
    }
}

在这种情况下：

protected int parent(int index){
        return (index-1)/2;
}

概括：

最小堆属性：

• 完整的二叉树结构。
• 父节点的值始终等于或小于其子节点。
• 通过数组实现，其中子级和父级的位置由基于索引的公式确定。

计算孩子和父母的位置：

• 左: leftChild = 索引 * 2 1
• 右: rightChild = 索引 * 2 2
• 父级：父级 = (索引 - 1) / 2

没有索引 0 的版本： 只需从计算中减去 1，结果是：

• leftChild = 索引 * 2
• rightChild = 索引 * 2 1
• 父级 = 索引 / 2

堆 - 最大堆

最高值位于根节点，因此父节点的值与其子节点相同或更大

孩子和家长的计算公式：

• 左: leftChild = 索引 * 2 1
• 右: rightChild = 索引 * 2 2
• 父级：父级 = (索引 - 1) / 2

插入

在末尾添加元素并向上冒泡，这会将元素与其父元素进行比较，并在必要时更改位置。 O(log n)。

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

消除

删除heapMax[0]元素，也就是根，然后取出最后一个元素并将其向上移动到根，调用sinkdown，然后将新元素从根向下推，直到找到正确的位置。

sinkDown需要保证父节点中的值大于等于子节点中的值。因此，当下沉一个节点时，它将与最大子节点进行比较。

在最小堆中，sinkDown必须确保父节点中的值小于或等于子节点的值。在本例中，将与最小的孩子进行比较。

parent = (indexDoFilho -1)/2

currentIndex = size-1

差异

• 在Max Heap中，sinkDown需要保证父节点中的值大于或等于子节点中的值。因此，当下沉一个节点时，它将与最大子节点进行比较。
• 在Max Heap中，如果父节点小于其子节点中最大的节点，那么它必须与最大的子节点交换，以确保最大值尽可能高。
• 在最小堆中，sinkDown必须确保父节点中的值小于或等于子节点的值。在本例中，将与最小的孩子进行比较。
• 在最小堆中，如果父节点大于子节点中最小的节点，就会发生切换，将最小值保留在顶部

以上是堆 - 最小和最大的详细内容。更多信息请关注PHP中文网其他相关文章！