二叉堆

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

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

在二叉堆里我們要求:

* 最小的元素在頂端

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

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

這樣一"堆"東西我們?cè)诔绦蛑性趺从媚?幸運(yùn)的是，二叉堆可以用一個(gè)簡(jiǎn)單的一維數(shù)組來(lái)存儲(chǔ)，如下圖所示。

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

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

* 添加元素

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

* 刪除元素

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

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

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

* 修改元素

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

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

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

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

#include

const int MAXN = 11111;

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

//以下兩個(gè)是自定義校驗(yàn)函數(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; }

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

template

class Heap

{

private:

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

public:

inline Heap() { clear(); }

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

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

{

int i;

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

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

{

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

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

else break;

}

a[i] = x;

}

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

{

int tmp, i;

n--;

//int x = a[0];

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

{

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

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;//定義一個(gè)堆，這里定義的是大根堆，如果要使用小根堆，把第二關(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;

}

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

如下圖的兩個(gè)堆:

1 11

/ \ / \

2 3 9 10

/ \ / \ / \ / \

4 5 6 7 5 6 7 8

/ \ / \ / \ / \

8 9 10 11 1 2 3 4

將這兩個(gè)堆保存在以1開(kāi)始的數(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

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

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

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

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

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

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