二叉堆基本操作

在二叉堆上可以進(jìn)行插入節(jié)點、刪除節(jié)點、取出值最小的節(jié)點、減小節(jié)點的值等基本操作。

形式上看，它從頂點開始，每個節(jié)點有兩個子節(jié)點，每個子節(jié)點又各自有自己的兩個子節(jié)點;數(shù)值上看，每個節(jié)點的兩個子節(jié)點都比它大或和它相等。

在二叉堆里我們要求:

* 最小的元素在頂端

* 每個元素都比它的父節(jié)點大，或者和父節(jié)點相等。

只要滿足這兩個條件，其他的元素怎么排都行。如上面的例子，最小的元素10在最頂端，第二小的元素20在10的下面，但是第三小的元素24在20的下面，也就是第三層，更大的30反而在第二層。

這樣一"堆"東西我們在程序中怎么用呢?幸運的是，二叉堆可以用一個簡單的一維數(shù)組來存儲，如下圖所示。

假設(shè)一個元素的位置是n(第一個元素的位置為1，而不是通常數(shù)組的第一個索引0)，那么它兩個子節(jié)點分別是 n × 2 和 n × 2 + 1 ，父節(jié)點是n除以2取整。比如第3個元素(例中是20)的兩個子節(jié)點位置是6和7(空)，父節(jié)點位置是1。

對于二叉堆我們通常有三種操作:添加、刪除和修改元素:

* 添加元素

首先把要添加的元素加到數(shù)組的末尾，然后和它的父節(jié)點(位置為當(dāng)前位置減去1再除以2取整(k-1)/2，比如第4個元素的父節(jié)點位置是1，第7個元素的父節(jié)點位置是3)比較，如果新元素比父節(jié)點元素大則交換這兩個元素，然后再和新位置的父節(jié)點比較，直到它的父節(jié)點不再比它小，或者已經(jīng)到達(dá)頂端，即第1的位置。

* 刪除元素

刪除元素的過程類似，只不過添加元素是"向上冒"，而刪除元素是"向下沉":刪除位置1的元素，把最后一個元素移到最前面，然后和它的兩個子節(jié)點比較，如果兩個子節(jié)點中較大的子節(jié)點大于此頂點，就將它們交換，直到兩個子節(jié)點都比此頂點小。

計算兩個子節(jié)點的位置的公式:左子節(jié)點:2K+1、右子節(jié)點:2K+2(注:這里針對的是根節(jié)點為零的情況，若根為1，則左右分別為2K與2K+1。

比如頂點為0，那么它的左右子節(jié)點分別為1和2位置，如果頂點為1，那么 1的左右兩個子節(jié)點即為3，4.以此類推

* 修改元素

和添加元素完全一樣的"向上冒"過程，只是要注意被修改的元素在二叉堆中的位置。

可以看出，使用二叉堆只需很少的幾步就可以完成排序，很大程度上提高了尋路速度。

二叉堆一般用數(shù)組來表示。例如，根節(jié)點在數(shù)組中的位置是0，第n個位置的子節(jié)點分別在2n+1和 2n+2。因此，第0個位置的子節(jié)點在1和2，1的子節(jié)點在3和4。以此類推。這種存儲方式便於尋找父節(jié)點和子節(jié)點。

如下圖的兩個堆:

1 11

/ \ / \

2 3 9 10

/ \ / \ / \ / \

4 5 6 7 5 6 7 8

/ \ / \ / \ / \

8 9 10 11 1 2 3 4

將這兩個堆保存在以1開始的數(shù)組中:

位置: 1 2 3 4 5 6 7 8 9 10 11

左圖: 1 2 3 4 5 6 7 8 9 10 11

右圖: 11 9 10 5 6 7 8 1 2 3 4

在C++的STL中提供了優(yōu)先隊列，定義方式為priority_queuepriq;默認(rèn)為每一次彈出隊列中最大的元素，與二叉堆性質(zhì)相似，很多時候可以直接當(dāng)作二叉堆使用。

當(dāng)然，也可以直接自己寫一個C++的類模板，以下是完整代碼:

#include

const int MAXN = 11111;

int n, a[MAXN], ans = 0;

//以下兩個是自定義校驗函數(shù)，mincmp是小根堆所需要的，而maxcmp就是大根堆所需要的了，

inline bool mincmp(const int &x, const int &y)

{ return x < y; }

inline bool maxcmp(const int &x, const int &y)

{ return x > y; }

//定義，第一個關(guān)鍵字為堆的大小，第二關(guān)鍵字為自定義校驗類型

template

class Heap

{

private:

int a[N], n;//n表示當(dāng)前元素的個數(shù)，同時也是最后一個元素的下一個指針

public:

inline Heap() { clear(); }

inline void clear() { n = 0; }//清空

inline void push(int x)//插入操作

{

int i;

n++;//元素個數(shù)相加

for(i = n - 1; i > 0; i = (i - 1) >> 1)//把這個元素和根節(jié)點比較并交換

{

if(cmp(x, a[(i - 1) >> 1]))

a[i] = a[(i - 1) >> 1];

else break;

}

a[i] = x;

}

inline void pop()//彈出操作，如果需要在彈出的同時返回總根節(jié)點，把void改成int，并加上下面的兩行被注釋部分

{

int tmp, i;

n--;

//int x = a[0];

for(i = 0; (i << 1) + 1 < n; i = tmp)

{

//比較左右子樹中更優(yōu)的一個交換(對于小根堆就是較小的那個，大根堆不解釋……)

tmp = ((i << 1) + 2 < n && cmp(a[(i << 1) + 2], a[(i << 1) + 1])) ? (i << 1) + 2 : (i << 1) + 1;

if(cmp(a[tmp], a[n]))

a[i] = a[tmp];

else

break;

}

a[i] = a[n];

//return x;

}

inline int top() { return a[0]; }//返回堆頂元素

inline bool empty() { return !n; }//判斷堆是否為空

};

Heap< MAXN, maxcmp > h;//定義一個堆，這里定義的是大根堆，如果要使用小根堆，把第二關(guān)鍵字換成上面的mincmp就可以了

int main()

{

scanf("%d", &n);

for (int i = 1; i <= n; i++)

{

scanf("%d", a + i);

h.push(a[i]);//壓入堆中

}

for (int i = 1; i <= n; i++)

{

printf("%d ", h.top());//從大到小輸出

h.pop();

}

return 0;

}

優(yōu)先隊列在信息學(xué)競賽中十分常見，在統(tǒng)計問題、最值問題、模擬問題和貪心問題等等類型的題目中，優(yōu)先隊列都有著廣泛的應(yīng)用。二叉堆是一種常用的優(yōu)先隊列，它編程簡單，效率高，但如果問題需要對兩個優(yōu)先隊列進(jìn)行合并，二叉堆的效率就無法令人滿意了。本文介紹的左偏樹，可以很好地解決這類問題。

左偏樹的定義和性質(zhì)

在介紹左偏樹之前，我們先來明確一下優(yōu)先隊列和可并堆的概念。

優(yōu)先隊列，可并堆

優(yōu)先隊列(Priority Queue)是一種抽象數(shù)據(jù)類型(ADT)，它是一種容器，里面有一些元素，這些元素也稱為隊列中的節(jié)點(node)。優(yōu)先隊列的節(jié)點至少要包含一種性質(zhì):有序性，也就是說任意兩個節(jié)點可以比較大小。為了具體起見我們假設(shè)這些節(jié)點中都包含一個鍵值(key)，節(jié)點的大小通過比較它們的鍵值而定。優(yōu)先隊列有三個基本的操作:插入節(jié)點(Insert)，取得最小節(jié)點(Minimum) 和刪除最小節(jié)點(Delete-Min)。

可并堆(Mergeable Heap)也是一種抽象數(shù)據(jù)類型，它除了支持優(yōu)先隊列的三個基本操作(Insert, Minimum,Delete-Min)，還支持一個額外的操作--合并操作: