参考动画：从堆的定义到优先队列、堆排序
建议配合动画食用
为什么叫堆呢？
“堆”这个词在数据结构的上下文中通常指的是一种特定的树形数据结构，其命名来源于它的特性和应用。在这种结构中，父节点和子节点之间存在特定的排序关系，这类似于物理世界中堆积的物体——较大或较重的物体（在堆排序中对应于较大或较小的值）位于顶部，而较小或较轻的物体则位于下方。
1、堆必须是完全二叉树
完全二叉树是一种特殊的二叉树，其中每个层级（除了可能的最后一个层级）都是完全填满的，并且最后一个层级的所有节点都尽可能地向左排列。这种结构使得堆可以用数组有效地表示，无需使用指针，节省空间。
由此可以推出：对于堆的父节点i，其子节点为2*I+1和2*i+2
2、堆序性
堆序性是指在堆中每个节点都必须满足特定的顺序关系。对于最大堆，任一节点的值都大于或等于其子节点的值。对于最小堆，则任一节点的值都小于或等于其子节点的值。
堆的基本操作
上滤和下滤（上浮与下沉）
- 上滤（上浮）： 在添加新元素或调整堆时使用，新元素添加到堆的末尾，然后与其父节点比较，如果不满足堆的性质，则与父节点交换，这一过程持续进行，直至恢复堆的性质。
- 下滤（下沉）： 在移除堆顶元素或调整堆时使用，将末尾元素移动到堆顶，然后与其子节点比较，如果不满足堆的性质，则与子节点中符合条件的那个交换，这一过程持续进行，直至恢复堆的性质。
代码：以大根堆为例
上浮操作
void shifup(vector<int>& heap,int index){
while(index>0){
int parent=(index-1)/2;
if(heap[index]<=heap[parent]) break;//对于大根堆
else swap(heap[index],heap[parent]);
index=parent;
}
}
下沉操作
void shifDown(vector<int>& heap,int index,int heapSize){
int leftChild,rightChild,largerChild;
while((leftChild=2*index+1)<heapSize){//循环时判断孩子节点是否在堆的范围内
rightChild=leftChild+1;
largerChild=leftChild;
if(rightChild<heapSize&&heap[rightChild]>heap[leftChild]){//判断左孩子还是右孩子大
largerChild=rightChild;
}
if(heap[index]>=heap[largerChild]) break;//大根堆
swap(heap[index],heap[larferChild]);
index=largerChild;
}
}
建堆
对于一个乱序的数组，如何建堆呢：
顶上滤顺序遍历，下下沉倒序遍历
自顶向下
方法：(以大根堆为例)
1、插入堆；
2、上滤
代码：
void siftUp(vector<int>& heap, int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (heap[index] <= heap[parent]) break;
swap(heap[index], heap[parent]);
index = parent;
}
}
void buildHeapTopDown(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++) {
siftUp(nums, i);
}
}
自下而上
1、先将所有元素建堆；
2、然后对每个父节点进行下滤操作；
3、先从第二层开始，最后在对根结点
为什么从 (n/2) - 1 开始： 在堆中，一个节点的子节点是 2*i + 1 和 2*i + 2（i 是父节点的索引）。因此，对于数组中的最后一个元素 n - 1，其父节点的索引是 (n - 1 - 1) / 2 = (n/2) - 1
void siftDown(vector<int>& heap, int index, int heapSize) {
int leftChild, rightChild, largerChild;
while ((leftChild = 2 * index + 1) < heapSize) {
rightChild = leftChild + 1;
largerChild = leftChild;
if (rightChild < heapSize && heap[rightChild] > heap[leftChild]) {
largerChild = rightChild;
}
if (heap[index] >= heap[largerChild]) break;
swap(heap[index], heap[largerChild]);
index = largerChild;
}
}
//这里是直接有一个完整的数组了
void buildHeapBottomUp(vector<int>& nums) {
int n = nums.size();
for (int i = (n - 2) / 2; i >= 0; i--) {
siftDown(nums, i, n);
}
}
总结
自下而上建堆方法的优势在于它利用了堆的完全二叉树特性，从底层开始逐步构造子堆，确保了每个子树自身都已经是一个合法的堆，然后再逐步合并这些小堆。这样，在处理父节点时，其子节点已经是有序的，只需要做少量必要的调整即可。因此，相比于自顶向下插入每个元素再逐一上滤的方法，自下而上的建堆方法更加高效。
简而言之：
自顶向下建堆
- 适用场景： 动态插入场景，如逐步加入新元素。
- 操作： 逐个将元素插入堆中，并通过上滤操作维护堆的性质。
- 时间复杂度： 大约为 O(nlogn)，其中 n 是数组元素的数量。这是因为每次插入操作的时间复杂度为 O(logn)，并且需要进行 n 次插入。
自下而上建堆
- 适用场景： 静态数组，当已有一个完整的数组并希望将其转化为堆。
- 操作： 从最后一个非叶子节点开始，逐次对每个节点执行下滤操作，将整个数组转化为堆。
- 时间复杂度： O(n)。这种方法比自顶向下建堆更高效，因为它更好地利用了已有的堆性质，尤其是在树的较低层。