堆

堆是一種在頻繁插入刪除情形下，仍能高效獲取序列最值的數據結構。堆頂為樹根，始終保持所有元素的最優值。堆總是一棵完全二叉樹，稱為二叉堆，因此其存儲結構中定位其子節點無需left和right。堆可分類為大根堆、小根堆。

在堆中的任意節點，其總<=(大根堆,less)或>=(小根堆,greater)其父節點的值。下面以小根堆為例。

堆的調整($O({\log }_{2}n)$)

上浮(堆底插入元素)

extern int heap[MAX],cnt;//cnt:堆底元素下標
void push(int x){
    heap[++cnt]=x;
    int i=cnt;//當前工作指針,上浮調整堆底元素
    while(i>1&&heap[i]<heap[i/2]){//大根堆為>
        swap(heap[i],heap[i/2]);
        i=i/2;
    }
}

下沉(彈出堆頂元素)

extern int heap[MAX],cnt;//cnt:堆底元素下標
void pop(){
    swap(heap[1],heap[cnt--]);//交換堆頂元素與堆底元素
    int i=1;//當前工作指針,下沉調整堆頂元素
    while(i<<1<=cnt){//確保至少有左子結點(完全二叉樹性質)
        int son=i<<1;
        if(son<cnt&&heap[son+1]<heap[son]) son++;//左右子節點中取最小的,充分確保可下沉,大根堆的第2個條件為>
        if(heap[son]<heap[i]) swap(heap[son],heap[i]),i=son;//大根堆為>
        else break;
    }
}

堆的構建

向上調整建堆($O(n{\log }_{2}n)$,在線)

對每個元素都調用$push$函數，共調用$n$次。

向下調整建堆(遍歷堆化,$O(n)$,離線)

算法流程：從最后一個葉子結點的父節點開始，倒序遍歷序列，利用堆的自相似性，每次執行下沉操作。

extern heap[MAX],cnt;
void shiftdown(int j){
    int i=j;
    while(i<<1<=cnt){
        int son=i<<1;
        if(son<cnt&&heap[son+1]<heap[son]) son++;
        if(heap[son]<heap[i]) swap(heap[son],heap[i]),i=son;
        else break;
    }
}
void build(){
    for(int i=cnt/2;i>=1;i--){
        shiftdown(i);
    }
}

STL(優先隊列)

堆可以用于實現優先隊列，C++的STLpriority_queue即為優先隊列，其獲取最值的功能與堆相同。

應用——堆排序($O(n{\log }_{2}n)$)

算法流程：建堆后，執行$n$次$pop$操作。