关于堆的构建和调整

堆的定义（以小顶堆为例）：

给定一个初始序列，在此基础上建堆。每个序列号（从1开始）为i的节点左孩子为2i，右孩子为2i+1. 小顶堆即为每个以当前节点为根节点的子树中，最小的值总是根节点的值。因此根据迭代思想，当前节点的值（设为a），与左右两子树相比较，使最小的节点值（设为b）成为根节点，即可保证在当前子树中最小的值一定是根节点。因此堆的整体调整是由下向上的过程。 当节点a经过调整位置下沉后，需要进行后续调整直至找到合适的位置或者抵达序列边界为止。因此单个节点的调整是由上而下的过程。

代码模板：

int heap[1001];//初始序列 void down_adjust(int x,int hi) {//单个节点 int i=x; int j=i*2; while(j<=hi){ if(j+1<=hi&&heap[j+1]<heap[j]){ j++; }; if(heap[j]<heap[i]){ swap(i,j); i=j; j=j*2; }else{ break;//此时该节点比左右孩子小，调整到了合适位置，退出调整 }; }; } void createheap(int n){//堆的整体调整 for(int i=n/2;i>=1;i--){ downadjust(i,n); }; }

另一种较为简便快速的建堆写法，即边输入边建堆： 单元调整由下往上，整体调整由上往下

void down_adjust(int x) { if (x == 1) { return; }; while (x > 1) { if (heap[x] < heap[x / 2]) { swap(x, x / 2); x = x / 2; } else { break; }; }; } void createheap(int n){ for (int i = 1; i <= n; i++) { cin >> heap[i]; down_adjust(i); }; }

---

堆的调整：

1，删除堆顶元素 即用堆的最后一个元素覆盖堆顶元素，再调整覆盖后根节点即可。调整完毕后序列规模减一。 2，向堆中添加一个元素 新添元素放在堆末尾，并将其向上调整一边。

---

注意

边输入边建堆与输入完成后在现成数组中建堆的结果会有不同。