堆是优先级列表的更高效版本。考虑到 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;
}
最小堆属性：
计算孩子和父母的位置：
没有索引 0 的版本： 只需从计算中减去 1，结果是：
最高值位于根节点，因此父节点的值与其子节点相同或更大
孩子和家长的计算公式：
在末尾添加元素并向上冒泡，这会将元素与其父元素进行比较，并在必要时更改位置。 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
以上是堆 - 最小和最大的详细内容。更多信息请关注PHP中文网其他相关文章！
