C++｜使用STL算法創建、調整、輸出最大堆、最小堆

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

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

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

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

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

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

代碼：

<code>#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\t",heap->heapData[i]);
    }
    printf("\n");
    while(!empty(heap))
    {
        printf("%d\t",popHeap(heap));
    }
    system("pause");
}
/*
10 9 6 7 8 2 5 1 4 3
10 9 8 7 6 5 4 3 2 1
*//<code>

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

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

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

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

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

具體細節見代碼和註釋：

<code>#include 
#include 
#include 
#include 
using namespace std;

void printVector(vector vc)
{
    copy(vc.begin(),vc.end(),ostream_iterator(cout," "));
	cout