# 堆 Heap ?

優先隊列(Priority Queue) ?

結構性:用 *數組* 表示的完全二叉樹; ?

有序性:任一結點的關鍵字是其子樹所有結點的最大值(或最小值) ?

? ? * “最大堆(MaxHeap)”,也稱“大頂堆”:最大值 ?

? ? * “最小堆(MinHeap)”,也稱“小頂堆” :最小值 ?

主要操作有: ?

? MaxHeap Create( int MaxSize ):創建一個空的最大堆。 ?

? Boolean IsFull( MaxHeap H ):判斷最大堆H是否已滿。 ?

? Insert( MaxHeap H, ElementType item ):將元素item插入最大堆H。 ?

? Boolean IsEmpty( MaxHeap H ):判斷最大堆H是否為空。 ?

? ElementType DeleteMax( MaxHeap H ):返回H中最大元素(高優先級)。 ?

## 結構

```c

typedef struct HNode *MaxHeap;

struct HNode {

? ? ElementType *Elements; // 存儲堆元素的數組

? ? int Size; ? // 堆的當前元素的個數

? ? int Capacity ?// 堆的最大容量

}

```

## 創建

```c

MaxHeap CreateHeap(int Maxsize)

{

? ? MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));

? ? H->Elements = malloc((MaxSize+1) * sizeof(ElementType)); // 因為這里是一個數組,需要分配空間

? ? H->Size = 0; // 當前是空的

? ? H->Capacity = MaxSize; ?// 堆的最大容量

? ? H->Elements[0] = MaxSize; /* 定義“哨兵”為大于堆中所有可能元素的值，便于以后操作 */

? ? return H;

}

```

## 插入

將新增結點插入到從其父結點到根結點的有序序列中 ?

將新item放在最后的位置Size+1, 然后跟他的父節點i/2比較,不斷把父節點往下(子節點)移動,直到其父節點大于item

```c

void InsertHeap(MaxHeap H, ElementType item)

{

? ? int i;

? ? if (IsFull(H)){

? ? ? ? printf("FULL\n");

? ? ? ? return;

? ? }

? ? i = ++H->Size; ?// H->Size++; i = H->Size; 把新增元素放在末尾H->Size++的位置上

? ? for(; H->Elements[i/2] < item; i/=2){ ?// 其父節點小于它

? ? ? ? H->Elements[i] = H->Elements[i/2]; // 把它的父節點,向下過濾, 插入的item向上過濾

? ? }

? ? // 當它的父結點[i/2]比它大的時候, 跳出循環

? ? H->Elements[i] = item; ?// 填上item

}

```

# 刪除 ?

取出根結點(最大值)元素，同時刪除堆的一個結點。 ?

* 最后的元素替補根的位置

* 有序化, 父結點和更大的那個子結點比較,將子結點不斷往上移, 直到父結點不子結點大 ?

```c

ElementType DeleteMax(MaxHeap H)

{

? ? int parent, child;

? ? ElementType MaxItem, temp;

? ? if(IsEmpty(H)){

? ? ? ? printf("Empty\n");

? ? ? ? return;

? ? }

? ? MaxItem = H->Elements[1]; // 取出最大值

? ? /* 用最大堆中最后一個元素從根節點開始向上過濾下層節點 */

? ? temp = H->Elements[Size]; ?// 把堆中最后一個值,交給temp

? ? Size--;

? ? for(parent=1; parent*2 <= H->Size; parent=child)

? ? {

? ? ? ? child = parent*2 ?// 左兒子

? ? ? ? /* child=左右兒子中大的那個, 當右兒子存在,且右兒子的值比左兒子大時,讓child=右兒子 */

? ? ? ? if((child!= H->Size) &&

? ? ? ? (H->Elements[child] < H->Elements[child+1]))

? ? ? ? ? ? child++;

? ? ? ?

? ? ? ? /* 當temp比child的值大時跳出循環 */

? ? ? ? if (temp >= Elements[child])

? ? ? ? ? ? break;

? ? ? ? else

? ? ? ? ? ? H->Elements[parent] = H->Elements[child]; //當parent < child,這個parent位置上變為child的值

? ? }

? ? H->Elements[parent] = temp;

? ? return MaxItem;

}

```

# 堆排序 ?

方法1:通過插入操作，將N個元素一個個相繼插入到一個初 始為空的堆中去，其時間代價最大為O(N logN)。

方法2:在線性時間復雜度下建立最大堆。O(N) ?

(1)將N個元素按輸入順序存入，先滿足完全二叉樹的結構特性 ?

(2)調整各結點位置，以滿足最大堆的有序特性。 ?

```c

void BuildHeap(MaxHeap H){

? ? int i;

? ? for(i = H->Size/2; i>0; i--)

? ? {// 從最后一個結點的父節點開始,到根節點為止

? ? ? ? PercDown(H, i);

? ? }

}

// 下濾函數, 將Maxheap中以H->Data[p]為根的子堆調整為最大堆

void PercDown( MaxHeap H, int p)

{

? ? int parent, child;

? ? X = H->Data[p]; // 取出根節點的值

? ? for(parent = ?p; parent*2 <= H->Size; parent = child)

? ? {

? ? ? ? child = parent * 2;

? ? ? ? if( (child != H->Size) && (H->Data[child] < H->Data[child+1]))

? ? ? ? {

? ? ? ? ? ? child++;

? ? ? ? }

? ? ? ? if (X > H->Data[child])

? ? ? ? ? ? break;

? ? ? ? else // 將X下濾

? ? ? ? ? ? H->Data[parent] = H->Data[child];

? ? }

? ? H->Data(parent) = X;

}

```

# 哈夫曼樹與哈夫曼編碼

帶權路徑WPL Weighted Path Length)長度最小, 最優二叉樹. ?

數據結構:

```c

typedef struct TreeNode *HuffmanTree;

struct TreeNode{

? ? int Weight;

? ? HaffmanTree left;

? ? HaffmantREE Right;

}

```

利用最小堆進行構造:

```c

HuffmanTree Huffman(MinHeap H)

{

? ? int i;

? ? HuffmanTree T;

? ? BuildMinHeap(H); // 將H->Elements[]按照權重調整為最小堆

? ? for(i=1; i < H->Size; i++) // 做size-1次合并

? ? {

? ? ? ? T = malloc(sizeof(struct TreeNode)); // 建立新結點

? ? ? ? /*從最小堆中刪除一個結點，作為新T的左子結點*/

? ? ? ? T->Left = DeleteMin(H);

? ? ? ? T->Right = DeleteMin(H);

? ? ? ? /*計算新權值*/

? ? ? ? T->Weight = T->Left->Weight+T->Right->Weight;

? ? ? ? Insert( H, T ); /*將新T插入最小堆*/

? ? }

? ? T = Deletemin(H); // 最小堆中的最后一個元素就是指向Huffman樹根節點的指針

? ? return T;

}

```

哈夫曼樹的特點:

1. 沒有度為1的結點

2. n個葉子結點的哈夫曼樹共有2n-1個結點; ?

? ? 因為: n2= n0 -1,

? ? 總結點數 = n0 + n2 = 2n0 - 1

3. 哈夫曼樹的任意非葉節點的左右子樹交換后仍是哈夫曼樹;

4. 對同一組權值{w1 ,w2 , ...... , wn}，存在不同構的兩

# 集合及運算 ?

雙親表示法: 孩子指向父節點 ?

數據結構

```c

typedef struct

{

? ? ElementType Data;

? ? int Parent; ?// 其父節點的下標

} SetType;

```

## 查找某個元素所在的集合 ?

用根節點表示

```c

int Find(SetType S[], ElementType X)

{

? ? /* 在數組S中查找值為X的元素所屬的集合, MaxSize為數組最大長度 */

? ? int i;

? ? for(i=0; i<MaxSize && S[i].Data != X; i++)

? ? if (i >= MaxSize) // 未找到

? ? ? ? return -1;

? ? for(; S[i].Parent >= 0; i = s[i].Parent); ?// 向上找它的父節點

? ? return i;

}

```

## 集合的并運算 ?

如果它們不同根，則將其中一個根結點的父結點指針設置成

? ?另一個根結點的數組下標。

```c

void Union( SetType S[], ElementType X1, ElementType X2 )

{

? ? int Root1, Root2;

? ? Root1 = Find(S, X1);

? ? Root2 = Find(S, X2);

? ? if( Root1 != Root2 )

? ? ? ? S[Root2].Parent = Root1;

}

```

為了使樹更矮,合并時按秩合并 ?

直接用一個數組表示,不用之前的數據結構了

```c

#define MAXN 1000 ? ? ? ? ? ? ? ? ?/* 集合最大元素個數 */

typedef int ElementType; ? ? ? ? ? /* 默認元素可以用非負整數表示 */

typedef int SetName; ? ? ? ? ? ? ? /* 默認用根結點的下標作為集合名稱 */

typedef ElementType SetType[MAXN]; /* 假設集合元素下標從0開始 */

SetName Find(SetType S, ElementType X){

? ? for(; S[X] > 0; X=S[X]);

? ? return X.

}

void OldUnion(SetType S, SetName Root1, SetName Root2){

? ? S[Root2] = Root1;

}

void Union( SetType S, SetName Root1, SetName Root2 )

{ /* 這里默認Root1和Root2是不同集合的根結點 */

? ? /* 保證小集合并入大集合 */

? ? if ( S[Root2] < S[Root1] ) { /* 如果集合2比較大 */

? ? ? ? S[Root2] += S[Root1]; ? ? /* 集合1并入集合2 ?*/

? ? ? ? S[Root1] = Root2;

? ? }

? ? else { ? ? ? ? ? ? ? ? ? ? ? ? /* 如果集合1比較大 */

? ? ? ? S[Root1] += S[Root2]; ? ? /* 集合2并入集合1 ?*/

? ? ? ? S[Root2] = Root1;

? ? }

}

```

路徑壓縮

```c

SetName Find( SetType S, ElementType X )

{

? ? if ( S[X] < 0 ) /* 找到集合的根 */

? ? ? ? return X;

? ? else

? ? ? ? return S[X] = Find( S, S[X] ); /* 路徑壓縮 */

}

```