由一维数组创建小根堆

1、结构体和头文件：

#include<iostream> #include<vector> using namespace std; struct MinHeap //也可以不用结构体，直接用vector<int> { vector<int> elem; int heapSize; MinHeap(vector<int> _elem) { elem.insert(elem.begin(),_elem.begin(),_elem.end()); heapSize = elem.size(); } };

2、打印：

void printMinHeap(MinHeap heap,int i,int k) { if(i < heap.heapSize) { printMinHeap(heap,2*i+2,k+5); //先打右子树 for(int j = 0; j < k; j++) { cout<<" "; } cout<<heap.elem[i]<<endl; printMinHeap(heap,2*i+1,k+5); } }

3、创建小根堆： 将有n个结点的完全二叉树，从最后一个分支节点(n-1)/2自底向上自底向上、由局部到整体调整为小根堆，siftDown是自顶向下"筛选"调整算法

void createMinHeap(MinHeap &h) { for(int i = (h.heapSize - 1)/2; i >= 0; i--) { siftDown(h,i,h.heapSize-1); } }

4、自顶向下"筛选"调整算法 从结点i开始到`m``为止，自上向下比较，如果子女的值小于双亲的值，则关键码小的上浮,继续向下层比较，否则不调整 ( 因为从最后一个分支结点开始构造小根堆，若结点i的子女比结点i的值大，则要么其左右子女是叶结点，要么是在前面被调整成了小根堆 )

int cnt = 1; void siftDown(MinHeap& h,int i, int m) // { int temp = h.elem[i]; for(int j = i*2+1; j <= m; j = 2*j+1) //j是i的左子女 { if(j < m && h.elem[j] > h.elem[j+1]) // j < m下标j+1在有效值内， { // h.elem[j]>h.elem[j+1]左子女大于右子女 j++; //根结点和右子女比较 } if(temp <= h.elem[j]) break; //开始时的根结点小于等于左右子女则不需要调整 else // temp > h.elem[j] { //开始时的根结点小于等于左右子女或者小于其子孙(第2次及以上循环时) h.elem[i] = h.elem[j]; //小的子女上移 i = j; // i 下降 } } h.elem[i] = temp; //回放temp暂存的元素 }

5、创建的全部代码：

#include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; struct MinHeap { vector<int> elem; int heapSize; MinHeap(vector<int> _elem) { elem.insert(elem.begin(),_elem.begin(),_elem.end()); heapSize = elem.size(); } }; void printMinHeap(MinHeap heap,int i,int k) { if(i < heap.heapSize) { printMinHeap(heap,2*i+2,k+5); //先打右子树 for(int j = 0; j < k; j++) { cout<<" "; } cout<<heap.elem[i]<<endl; printMinHeap(heap,2*i+1,k+5); } } int cnt = 1; void siftDown(MinHeap& h,int i, int m) //自定向下"筛选"调整算法 { //从结点i开始到m为止，自上向下比较，如果子女的值小于双亲的值，则关键码小的上浮 //继续向下层比较，否则不调整(因为从最后一个分支结点开始构造小根堆，若结点i的子女比 //结点i的值大，则要么其左右子女是叶结点，要么是在前面被调整成了小根堆 cout<<"第"<<cnt<<"次调整:(i == "<<i<<endl; printMinHeap(h,0,0); int temp = h.elem[i]; for(int j = i*2+1; j <= m; j = 2*j+1) //j是i的左子女 { if(j < m && h.elem[j] > h.elem[j+1]) // j < m下标j+1在有效值内， { // h.elem[j]>h.elem[j+1]左子女大于右子女 j++; //根结点和右子女比较 } if(temp <= h.elem[j]) break; //开始时的根结点小于等于左右子女则不需要调整 else // temp > h.elem[j] { //开始时的根结点小于等于左右子女或者小于其子孙(第2次及以上循环时) h.elem[i] = h.elem[j]; //小的子女上移 i = j; // i 下降 } } h.elem[i] = temp; //回放temp暂存的元素 cout<<"第"<<cnt++<<"次调整后:(i == "<<i<<endl; printMinHeap(h,0,0); cout<<endl; } void createMinHeap(MinHeap &h) {//将一个数组自底向上、由局部到整体调整为小根堆， for(int i = (h.heapSize - 1)/2; i >= 0; i--) { siftDown(h,i,h.heapSize-1); } } int main() { vector<int> arr = {53,17,78,9,45,65,87,23}; MinHeap heap(arr); createMinHeap(heap); printMinHeap(heap,0,0); return 0; }

调试输出:

第1次调整:(i == 3) 87 78 65 53 45 17 9 23 第1次调整后:(i == 3) 87 78 65 53 45 17 9 23 第2次调整:(i == 2) 87 78 65 53 45 17 9 23 第2次调整后:(i == 5) 87 65 78 53 45 17 9 23 第3次调整:(i == 1) 87 65 78 53 45 17 9 23 第3次调整后:(i == 3) 87 65 78 53 45 9 17 23 第4次调整:(i == 0) 87 65 78 53 45 9 17 23 第4次调整后:(i == 7) 87 65 78 9 45 17 23 53 87 65 78 9 45 17 23 53

6、插入新元素: 新结点总是插入到已经建成的小根堆的后面。因此，只要从最后一个结点沿它双亲的路径,自下向上比较,双亲比子女大，就和子女对调。

void insert(MinHeap &heap,int value) { heap.elem.push_back(value); //插在最后 siftUp(heap,heap.elem.size()); heap.heapSize++; } void siftUp(MinHeap &heap,int start) { //从结点start开始到结点0为止，自下向上比较，如果子女的值小于双亲的值则双亲 //的值下降,再用子女的值继续向上比较 int temp = heap.elem[start]; //暂存新插入结点的值，用来跟双亲(祖先比较) int i = start; // i指向子女 int j = (i-1)/2; // j指向双亲 while(i > 0) { if(heap.elem[j] <= temp) //双亲的值小不调整 { break; } else //双亲的值大 { heap.elem[i] = heap.elem[j]; //双亲下移 i = j; //i指向子女，i上升 j = (j-1)/2; // j指向双亲 } } heap.elem[i] = teap; //存回子女 }

8、小根堆删除元素 删除一般是删除小根堆的最小元素,即其完全二叉树的顺序表示的第0号元素。

bool remove(MinHeap &heap,int &x) //小根堆删除算法 { if(heap.heapSize == 0) return false; x = heap.elem[0]; heap.elem[0] = heap.elem[heap.heapSize-1]; //最后元素填到补第一根结点 heap.elem.pop_back(); heap.heapSize--; siftDown(heap,0,heap.heapSize-1); //自上向下调整为小根堆 return true; //删除成功 }

---

9、补充： 可以看出大小根堆的一个应用就是优先队列。