最大堆(又叫大根堆、大頂堆)和最小堆是二叉堆的兩種形式，一類很重要的數據結構，如用于堆排序等。

最小堆：根結點的鍵值是所有堆結點鍵值中最小者，且每個結點的值都比其孩子的值小。

最大堆：根結點的鍵值是所有堆結點鍵值中最大者，且每個結點的值都比其孩子的值大。

下面以大根堆為例，來說明其入堆和出堆的操作：

入堆，插入：向上滲透(先是插入堆的最后位置，然后按最大堆的規則調整到適當位置)；

出堆，刪除：向下滲透(第一個元素出堆，從第二層開始，較大的元素往上滲透，將最后一個元素賦值給倒數第二層上的當前元素。

代碼：

#include using namespace std;const int MAX = 55;typedef struct Heap{ int sizeHeap; int* heapData;}HEAP,*LPHEAP;LPHEAP createHeap(){ LPHEAP heap=(LPHEAP)malloc(sizeof(HEAP)); heap->sizeHeap=0; heap->heapData=(int*)malloc(sizeof(int)*MAX); return heap;}int size(LPHEAP heap){ return heap->sizeHeap;}int empty(LPHEAP heap){ return heap->sizeHeap==0;}void moveToCorrectPos(LPHEAP heap, int curPos)//向上滲透，curPos一般取最后一個元素的下標{ while(curPos>1) { int Max=heap->heapData[curPos]; int parentIndex=curPos/2; if(Max>heap->heapData[parentIndex]) { heap->heapData[curPos]=heap->heapData[parentIndex]; heap->heapData[parentIndex]=Max; curPos=parentIndex;//向上移動 } else { break; } }}void insertHeap(LPHEAP heap, int data) // 放到當前堆的最后面并按條件往上移{ ++heap->sizeHeap; heap->heapData[heap->sizeHeap]=data; moveToCorrectPos(heap,heap->sizeHeap);}int popHeap(LPHEAP heap){ int Max=heap->heapData[1]; int curPos=1; int childIndex=curPos*2; while(childIndex<=heap->sizeHeap) { int temp = heap->heapData[childIndex]; if(childIndex+1<=heap->sizeHeap && tempheapData[childIndex+1]) { temp=heap->heapData[++childIndex]; } heap->heapData[curPos]=temp; curPos=childIndex;//下移一層 childIndex*=2; } heap->heapData[curPos]=heap->heapData[heap->sizeHeap]; --heap->sizeHeap; return Max;}void main(){ LPHEAP heap=createHeap(); for(int i=1;i<11;++i) { insertHeap(heap,i); } for(i=1;i<11;++i) { printf("%d",heap->heapData[i]); } printf(""); while(!empty(heap)) { printf("%d",popHeap(heap)); } system("pause");}/*10 9 6 7 8 2 5 1 4 310 9 8 7 6 5 4 3 2 1*/

在STL算法庫中，有一簇函數專門用來將某一個序列容器調整為大堆或小堆：

(以下函數參數_Compare，可以是less<>()，與大頂堆相關；或者greater<>()，與小頂堆相關)

make_heap(_RAIter,_RAIter,_Compare)： 生成大頂堆或小頂堆；

push_heap(_RAIter,_RAIter,_Compare) ：如果有向堆(容器)中插入(.push_back())元素，需要使用此函數來調整大堆或小堆；

pop_heap(_RAIter,_RAIter,_Compare) ：將堆(容器)中的第一個元素與最后一個元素交換，除最后一個元素以外，前面的元素按大堆或小堆規則調整。由此，如果刪除(.pop_back())最后一個元素，剩下的元素又是一個大堆或小堆。

具體細節見代碼和注釋：

#include #include #include #include using namespace std;void printVector(vector vc){ copy(vc.begin(),vc.end(),ostream_iterator(cout," "));cout<b;}bool lesser(int a,int b){return a vc, FP fp){//int n = hv.size(); //for(int i=0;i bigHeap;bigHeap.assign(dim,dim+cnt); cout<())make_heap(bigHeap.begin(),bigHeap.end(),less()); // 缺省less()cout< smallHeap;smallHeap.assign(dim,dim+cnt);// 使用vector建立小堆(greater())make_heap(smallHeap.begin(),smallHeap.end(),greater());cout<());cout<

－End－

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的大顶堆删除最大值_C++｜使用STL算法创建、调整、输出最大堆、最小堆的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。