數據結構基礎知識: 表棧隊列樹散列堆

2019 年 11 月 21 日
筆記

1. 表，棧和隊列

表，棧和隊列是電腦科學中最簡單和最基本的三種底層數據結構。事實上，每一個有意義的程式都將明晰地至少使用一種這樣的數據結構，而棧則在程式中總是要間接地用到，不管你在程式中是否做了聲明。

1.1 抽象數據類型（ADT）

在電腦軟體編程中，我們會接觸到諸如整型，浮點型，字元型，布爾型等基本數據類型，也有一些更為複雜的複合數據類型，如數組，字典（散列表），元組等。如果我們拋開這些數據類型具體實現，進一步抽象，給出更一般的定義，即每一種數據類型實際是一些特定操作的集合。我們稱這些操作的集合為抽象數據類型（abstract data type, ADT）。ADT 是數學意義上的抽象，它不約束各個操作的具體實現，對於每種 ADT 並不存在什麼法則來告訴我們必須要有哪些操作，這只是一個設計決策。

1.2 表ADT

表是一種形如 A_1, A_2, A_3, ldots, A_N 的數據結構。我們說這個表的大小是 N 。我們稱大小為 0 的表為空表(empty list)。對於除空表以外的任何錶，我們說 A_{i+1}(i<N) 後繼 A_i （或繼 A_i 之後）並稱 A_{i-1}(i>1) 前驅 A_i 。定義表ADT的操作集合通常包含：

PrintList: 列印表
MakeEmpty: 返回空表
Find: 返回關鍵字(key)首次出現的位置
Insert: 從表的指定位置插入關鍵字(key)
Delelte: 從表的指定位置刪除關鍵字(key)
FindKth: 返回指定位置上的元素

1.2.1 簡單數組實現

我們最容易想到實現表的方法就是數組。使用數組實現表的各項操作，顯而易見的時間複雜度是:

PrintList: O(N)
Find: O(N)
FindKth: O(1)
Insert: O(N)
Delete: O(N)

我們不難發現，當插入和刪除 N 個元素時，需要花費 O(N^2) 的時間，運行慢且表的大小必須事先已知。因此當需要具有插入和刪除操作時，通常不使用簡單數組來實現。

1.2.2 鏈表實現

為了避免插入和刪除的線性開銷，我們需要允許表可以不連續存儲，否則表的部分或全部需要整體移動。因此，這種情況下更好的實現方式是鏈表(linked list)。

鏈表由一系列不必在記憶體中相連的結構組成。每一個結構均含有表元素和指向包含該元素後繼元的結構的指針。我們稱之為Next指針。最後一個單元的Next指針指向Null。鏈表分為：單鏈表，雙鏈表，循環鏈表。

鏈表的 C 語言實現：

#include <stdlib.h>    struct Node  {      int Element;      Node* Next;  };    int  IsEmpty(Node* L)  {      return L->Next == NULL;  }    int  IsLast(Node* P, Node* L)  {      return P->Next == NULL;  }    Node*  Find(int x, Node* L)  {      Node* P;      P = L->Next;      while(P != NULL && P->Element != x)          P = P->Next;      return P;  }    Node*  FindPrevious(int x, Node* L)  {      Node* P;        P = L;      while(P->Next != NULL && P->Next->Element != x)          P = P->Next;        return P;  }    void  Delete(int x, Node* L)  {      Node* P;      Node* TmpCell;        P = FindPrevious(x, L);        if (!IsLast(P, L)) {          TmpCell = P->Next;          P->Next = TmpCell->Next;          free(TmpCell);      }  }    void  Insert(int x, Node* L, Node* P)  {      Node* TmpCell;        TmpCell = (Node*)malloc(sizeof(struct Node));        if (TmpCell != NULL)          printf("Out of space!!!");        TmpCell->Element = x;      TmpCell->Next = P->Next;      P->Next = TmpCell;  }    void  DeleteList(Node* L)  {      Node* P;      Node* Tmp;      P = L->Next;      L->Next = NULL;      while(P != NULL)      {          Tmp = P->Next;          free(P);          P = Tmp;      }  }

1.2 棧ADT

棧（stack）是限制插入和刪除只能在一個位置上進行的表，該位置是表的末端，叫做棧的頂（top）。對棧的基本操作有Push(進棧)和Pop(出棧)，前者相當於插入，後者則是刪除最後插入的元素。最後插入的元素可以通過使用Top操作在執行Pop之前讀取。

由於棧是一個表，因此任何實現表的方法都能實現棧。通常使用數組是一個較為簡便的方法。

1.3 隊列ADT

和棧一樣，隊列（queue）也是表。不同的是，使用隊列時插入在一端進行而刪除則在另一端進行。

隊列的基本操作是Enqueue (入隊)，它是在表的末端（rear 隊尾）插入一個元素，還有 Dequeue （出隊），它是刪除（或返回）在表的開頭（front 對頭）的元素。

2. 樹

2.1 基礎知識

對於大量的輸入數據，鏈表的線性訪問時間太慢，不宜使用。而「樹」大部分操作的運行時間平均為 O(log N) 。

一課樹是 N 個節點 N-1 條邊的集合，其中的一個節點叫做根。

路徑

從節點 n_1 到 n_k 的路徑（path）定義為節點 n_1, n_2, …, n_k 的一個序列，使得對於 1 le i < k ,節點 n_i 是 n_{i+1} 的父親。這個路徑的長（length）為該路徑上的邊的條數，即 k-1 。從每一個節點到它自己都有一條長為 0 的路徑。從根到每個節點有且僅有一條路徑。

深度

對於任意節點 n_i ， n_i 的深度（depth）為從根到 n_i 的唯一路徑的長。因此，根的深度為 0 。

高度

n_i 的高（height）是從 n_i 到一片樹葉的最長路徑的長。因此，所有樹葉的高度都是 0 。

祖先（ancestor）和後裔（descendant）

如果存在從 n_1 到 n_2 的一條路徑，那麼 n_1 是 n_2 的一位祖先而 n_2 是 n_1 的一個後裔。如果 n_1 ne n_2 ，那麼 n_1 是 n_2 的一位真祖先（proper ancestor）而 n_2 是 n_1 的一個真後裔（proper descendant）。

2.2 樹的實現

將每個節點的所有兒子都放在樹節點的鏈表中。FirstChild 是指向第一個兒子的指針，NextSibling 指向下一個兄弟節點。

typedef struct TreeNode *PtrToNode;    struct TreeNode  {      ElementType Element;      PtrToNode FirstChild;      PtrToNode NextSibling;  }

2.3 樹的遍歷

先序遍歷（preorder traversal）

在先序遍歷中，對節點的處理工作是在它的諸兒子節點被處理之前進行的。例如：列印目錄樹形結構圖，先列印父節點，再遞歸列印子節點。

後序遍歷（postorder traversal）

在後序遍歷中，在一個節點處的工作是在它的諸兒子節點被計算後進行的。例如：計算目錄所佔磁碟空間，在得到父節點佔用空間前，需要先遞歸計運算元節點所佔用的磁碟空間，最後才能逐級向上得到根節點的磁碟總佔用空間。

中序遍歷（inorder traversal）

用於二叉樹。遍歷順序：左子樹，節點，右子樹。

2.4 二叉樹（binary tree）

在二叉樹中，每個節點最多只有兩個兒子。

二叉樹的平均深度為 O(sqrt{N}) ，而對於特殊類型的二叉樹，如二叉查找樹（binary search tree）,其平均深度是 O(log N) 。

2.4.1 二叉樹實現

因為一棵二叉樹最多有兩個兒子，所以我們可以用指針直接指向它們。樹節點的聲明在結構上類似於雙鏈表的聲明。在聲明中，一個節點就是由Key資訊加上兩個指向其他節點的指針（Left 和　Right）組成的結構。

typedef struct TreeNode *PtrToNode;  typedef struct PtrToNode Tree;    struct TreeNode  {      ElementType Element;      Tree Left;      Tree Right;  }

二叉樹有許多與搜索無關的重要應用。二叉樹的主要用處之一是在編譯器的設計領域。如二元表達式樹。

2.4.2 查找樹ADT——二叉查找樹

二叉樹的一個重要的應用是它們在查找中的使用。使二叉樹成為二叉查找樹的性質是，對於樹中的每個節點 X ，它的左子樹所有關鍵字的值小於 X ，而它右子樹中所有關鍵字值大於 X 的關鍵字值。

操作集合：

MakeEmpty
Find
FindMin 和 FindMax
Insert
Delete

2.4.3 AVL 樹

AVL（Adelson-Velskii 和 Landis）樹是帶有平衡條件的二叉查找樹。這個平衡條件必須要容易保持，而且它必須保證樹的深度是 O(log N) 。最簡單的想法是要求左右子樹具有相同的高度。另一種平衡條件是要求每個節點都必須要有相同高度的左子樹和右子樹。雖然這種平衡條件保證了樹的深度小，但是它太嚴格，難以使用，需要放寬條件。

一棵AVL樹是其每個節點的左子樹和右子樹的高度最多差1的二叉查找樹。

單旋轉

雙旋轉

2.4.4 伸展樹（splay tree）

伸展樹保證從空樹開始任意連續 M 次對樹的操作最多花費 O(M log N) 的時間。

2.5 B-樹

雖然迄今為止我們所看到的查找樹都是二叉樹，但是還有一種常用的查找樹不是二叉樹。這種樹叫做B-樹（B-tree）。

階為 M 的B-樹是一棵具有下列結構特性的樹：

樹的根或者是一片樹葉，或者其兒子數在2和M之間。
除根外，所有非樹葉節點的兒子數在[ M/2 ]和 M 之間。
所有的樹葉都在相同的深度上。

B-樹實際用於資料庫系統，在那裡樹被存儲在物理的磁碟上而不是主存中。一般來說，對磁碟的訪問要比任何的主存操作慢幾個數量級。如果我們使用M階B-樹，那麼磁碟訪問的次數是 O(log_{M}N)

3. 散列

散列表的實現常常叫做散列（hashing）。散列是一種用於以常數平均時間執行插入，刪除和查找的技術。但是，那些需要元素間任何排序資訊的操作將不會得到有效的支援。因此，諸如 FindMin，FindMax 以及以線性時間按排序順序將整個表進行列印的操作都是散列所不支援的。

3.1 一般想法

理想的散列表數據結構只不過是一個包含關鍵字（key）的具有固定大小的數組。典型情況下，一個關鍵字就是一個帶有相關值（例如工資資訊）的字元串。我們把表的大小記作Table-Size，並將其理解為散列數據結構的一部分而不僅僅是浮動於全局的某個變數。通常的習慣是讓表從0到Table-Size - 1變化。

每個關鍵字被映射到從0到Table-Size - 1這個範圍中的某個數，並且被放到適當的單元中。這個映射就叫做散列函數（hash function）。理想情況下它應該運算簡單並且應該保證任何兩個不同的關鍵字映射到不同的單元。不過，這是不可能的，因為單元的數目是有限的，而關鍵字實際上是用不完的。因此，我們尋找一個散列函數，該函數要在單元之間均勻地分配關鍵字。這就是散列的基本想法。剩下的問題則是選擇一個函數，決定當兩個關鍵字散列到同一個值的時候（稱為衝突collision）應該做什麼以及如何確定散列表的大小。

3.2 散列函數

3.2.1 輸入整數關鍵字

如果輸入的關鍵字是整數，則一般合理的方法就是直接返回「Key mod TableSize」（關鍵字對錶大小取模）的結果，除非Key碰巧具有某些不理想的性質。例如，若表的大小是10，而關鍵字都以0為個位，這意味所有關鍵字取模運算的結果都是0（都能被10整除）。這種情況，好的辦法通常是保證表的大小是素數（也叫質數，只能被1和自身整除）。當輸入的關鍵字是隨機的整數時，散列函數不僅算起來簡單而且關鍵字的分配也很均勻。

3.2.2 輸入字元串關鍵字

通常，關鍵字是字元串；在這種情形下，散列函數需要仔細地選擇。

一種方法是把字元串中字元的ASCII碼值加起來。以下該方法的C語言實現。

typedef unsigned int Index;    Index  Hash(const char *Key, int TableSize)  {      unsigned int HashVal = 0;      while(*Key != '')          HashVal += *Key++;      return HashVal % TableSize;  }

這種方法實現起來簡單而且能很快地計算出答案。不過，如果表很大，則函數將不會很好地分配關鍵字。例如，設 TableSize = 10007 （10007是素數），並設所有的關鍵字至多8個字元長。由於char型量的值最多是127，因此散列函數只能取在0和1016之間，其中 1016=127times8 。這顯然不是一種均勻分配。

第二種方法。假設Key至少有兩個字元外加NULL結束符。值27表示英文字母表的字母個數外加一個空格，而 729=27^2 。該函數只考查前三個字元，假如它們是隨機的，而表的大小像前面那樣還是10007，那麼我們就會得到一個合理的均衡分配。

Index  Hash(const char *Key, int TableSize)  {      return (Key[0] + 27*Key[1] + 729*Key[2]) % TableSize;  }

可是不巧的是，英文並不是隨機的。雖然3個字元（忽略空格）有 26^3 = 17576 種可能組合，但查驗辭彙量足夠大的聯機詞典卻揭示：3個字母的不同組合數實際只有2851。即使這些組合沒有衝突，也不過只有表的28%被真正散列到。因此，雖然很容易計算，但是當散列表足夠大的時候這個函數還是不合適的。

一個更好的散列函數。這個散列函數涉及到關鍵字中的所有字元，並且一般可以分布得很好。計算公式如下：

sum_{i=0}^{KeySize-1} Key[KeySize-1-i]cdot32^i

它根據Horner法則計算一個（32的）多項式。例如，計算 h_k=k_1 + 27k_2 + 27^2k_3 的另一種方式是藉助於公式 h_k=(k_3 times 27 + k_2)times 27 + k_1 進行。Horner法則將其擴展到用於 n 次多項式。

Index  Hash(const char *Key, int TableSize)  {      unsigned int HashVal = 0;        while(*Key != '')                     /* 1 */          HashVal = (HashVal << 5) + *Key++;  /* 2 */      return HashVal % TableSize;             /* 3 */  }

這裡之所以用 32 替代27，是因為用32作乘法不是真的去乘，而是移動二進位的5位。為了運算更快，程式第2行的加法可以用按位異或來代替。雖然就表的分布而言未必是最好的，但確實具有及其簡單的優點。如果關鍵字特別長，那麼該散列函數計算起來將會花費過多的時間，不僅如此，前面的字元還會左移出最終的結果。這種情況，通常的做法是不使用所有字元。此時關鍵字的長度和性質將影響選擇。

3.3 衝突解決

解決了關鍵字均勻映射的問題，剩下的主要編程細節是解決衝突的消除問題。如果當一個元素被插入時另一個元素已經存在（散列值相同），那麼就產生了衝突，這種衝突需要消除。解決這種衝突的方法有幾種。最簡單的兩種是：分離鏈接法和開放定址法。

3.3.1 分離鏈接法（separate chaining）

分離鏈接法是將散列到同一個值的所有元素保留到一個表中。為了方便起見，這些表都有表頭，實現方法與表ADT相同。如果空間很緊，則更可取的方法是避免使用這些表頭。

類型聲明：

#ifndef _HashSep_H    struct ListNode;  typedef struct ListNode *Position;  struct HashTbl;  typedef struct HashTbl *HashTable;    HashTable InitializeTable(int TableSize);  void DestroyTable(HashTable H);    ElementType Retrieve(Position P);    #endif    struct ListNode  {      ElementType Element;      Position Next;  };    typedef Position List;    struct HashTbl  {      int TableSize;      List *TheLists;  };

初始化函數：

HashTable  InitializeTable(int TableSize)  {      HashTable H;      int i;        if (TableSize < MinTableSize)      {          Error("Table size too small");          return NULL;      }        H = malloc(sizeof(struct HashTbl));      if (H == NULL)          FatalError("out of space!!!");        H->TableSize = NextPrime(TableSize);                /* 1 設置素數大小 */      H->TheLists = malloc(sizeof(List) * H->TableSize);  /* 2 */      if (H->TheLists == NULL)          FatalError("Out of space!!!");        /**        * 分配鏈表表頭        *        * 給每一個表設置一個表頭，並將 Next 指向 NULL。如果不用表頭，以下程式碼可省略。        */      for(i = 0; i < H->TableSize; i++)      {          H->TheLists[i] = malloc(sizeof(struct ListNode)); /* 3 */          if (H->TheLists[i] == NULL)              FatalError("Out of space!!!");          else              H->TheLists[i]->Next = NULL;      }        return H;  }

以上程式低效之處是標記為3處malloc執行了H->TableSize次。這可以通過循環開始之前調用一次malloc操作：

H->TheLists = malloc(sizeof(struct ListNode) * H->TableSize);

Find 操作：

Position  Find(ElementType Key, HashTable H)  {      Position P;      List L;        L = H->TheLists[ Hash(Key, H->TableSize) ];      P = L->Next;      while(P != NULL && P->Element != Key)   /* ElementType 為 int時比較。字元串比較使用 `strcmp` */          P = P->Next;        return P;  }

注意，判斷 P->Element != Key，這裡適用於整數。字元串比較用 strcmp 替換。

Insert 操作：

void  Insert(ElementType Key, HashTable H)  {      Position Pos, NewCell;      List L;        Pos = Find(Key, H);      if (Pos == NULL)      {          NewCell = malloc(sizeof(struct ListNode));          if(NewCell == NULL)              FatalError("Out of space!!!");          else          {              L = H->TheLists[ Hash(Key, H->TableSize) ];              NewCell->Next = L->Next;              NewCell->Element = Key;              L->Next = NewCell;          }      }  }

如果在散列中諸常式中不包括刪除操作，那麼最好不要使用表頭。因為這不僅不能簡化問題而且還要浪費大量的空間。

3.3.2 開放定址法（Open addressing hashing）

類型聲明：

#ifndef _HashQuad_H    typedef unsigned int Index;  typedef Index Position;    struct HashTbl;  typedef struct HashTbl *HashTable;    HashTable InitializeTable(int TableSize);  void DestroyTable(HashTable H);  Position Find(ElementType Key, HashTable H);  void Insert(ElementType Key, HashTable H);  ElementType Retrieve(Position P, HashTable H);  HashTable Rehash(HashTable H);    #endif    enum KindOfEntry { Legitimate, Empty, Deleted };    struct HashEntry  {      ElementType Element;      enum KindOfEntry Info;  };    typedef struct HashEntry Cell;    struct HashTbl  {      int TableSize;      Cell *TheCells;  };

初始化開放定址散列表:

HashTable  InitializeTable(int TableSize)  {      HashTable H;      int i;        if (TableSize < MinTableSize)      {          Error("Table size too small");          return NULL;      }        /* 給散列表分配記憶體 */      H = malloc(sizeof(struct HashTbl));      if (H == NULL)          FatalError(Out of space!!!);        H->TableSize = NextPrime(TableSize);    /* 大於 TableSize 的第一個素數 */        /* 給數組所有單元分配記憶體 */      H->TheCells = malloc(sizeof(Cell) * H->TableSize);      if(H->TheCells == NULL)          FatalError("Out of space!!!");        for (i = 0; i < H->TableSize; i++)          H->TheCells[i].Info = Empty;        return H;  }

Find 操作：

Position  Find(ElementType Key, HashTbl H)  {      Position CurrentPos;      int CollisionNum;        CollisionNum = 0;      CurrentPos = Hash(Key, H->TableSize);      while(H->TheCells[CurrentPos].Info != Empty &&            H->TheCells[CurrentPos].Element != Key)            /* 這裡可能需要使用 strcmp 字元串比較函數 !! */      {          CurrentPos += 2 * ++CollisionNum - 1;          if (CurrentPos >= H->TableSize)              CurrentPos -= H->TableSize;      }        return CurrentPos;  }

Insert 操作：

void Insert(ElementType Key, HashTable H)  {      Position Pos;      Pos = Find(Keu, H);      if (H->TheCells[Pos].Info != Legitimate)      {          H->TheCells[Pos].Info = Legitimate;          H->TheCells[Pos].Element = Key; /* 字元串類型需要使用 strcpy 函數 */      }  }

3.4 散列表的應用

散列有著豐富的應用。編譯器使用散列表跟蹤源程式碼中聲明的變數。這種數據結構叫做符號表(symbol table)。散列表是這種問題的理想應用，因為只有Insert和Find操作。標識符一般都不長，因此其散列函數能夠迅速被算出。

散列表常見的用途也出現在為遊戲編寫的程式中。當程式搜索遊戲的不同的行時，它跟蹤通過電腦基於位置的散列函數而看到的一些位置。如果同樣的位置再出現，程式通常通過簡單移動變換來避免昂貴的重複計算。遊戲程式的這種一般特點叫做變換表(transposition table)。

另外一個用途是在線拼寫檢驗程式。如果錯拼檢測（與糾正錯誤相比）更重要，那麼整個詞典可以被預先散列，單詞則可以在常數時間內被檢測。散列表很適合這項工作，因為以字母順序排列單詞並不重要；而以它們在文件中出現的順序顯示出錯誤拼寫當然是可以接受的。

4. 優先隊列（堆）

4.1 為什麼需要優先隊列？

隊列是一種先進先出的表ADT，正常來說，先入隊的元素，會先出隊，意味沒有那個元素是特殊的，擁有「插隊」的優先權。這種平等，並不試用所有場景。有時，我們希望隊列中某類元素擁有比其他元素更高的優先順序，以便能提前得到處理。因此，我們需要有一種新的隊列來滿足這樣的應用，這樣的隊列叫做「優先隊列（priority queue）」。

4.2 優先隊列模型

優先隊列允許至少兩種操作：Insert(插入) ，以及 DeleteMin(刪除最小者)。Insert 操作等價於 Enqueue(入隊)，而 DeleteMin 則是隊列中 Dequeue(出隊) 在優先隊列中的等價操作。DeleteMin 函數也變更它的輸入。

4.3 簡單實現

4.3.1 單鏈表實現

在表頭以 O(1) 執行插入操作，並遍歷該鏈表以刪除最小元，這又需要 O(N) 時間。另一種做法是，始終讓表保持排序狀態；這使得插入代價高昂（ O(N) ）而DeleteMin花費低廉（ O(1) ）。基於DeleteMin的操作次數從不多於插入操作次數的事實，前者也許是更好的辦法。

4.3.2 二叉查找樹實現

使用二叉查找樹，Insert 和 DeleteMin 這兩種操作的平均運行時間都是 O(log N) 。

4.4 二叉堆（binary heap）

實現優先隊列更加普遍的方法是二叉堆，以至於當堆(heap)這個詞不加修飾地使用時一般都是指該數據結構(優先隊列)的這種實現。因此，我們單獨說堆時，就是指二叉堆。同二叉查找樹一樣，堆也有兩個性質，即結構性和堆序性。正如AVL樹一樣，對堆的一次操作可能破壞這兩個性質的一個，因此，堆的操作必須要到堆的所有性質都被滿足時才能終止。事實上這並不難做到。

4.4.1 結構性質

堆是一棵被完全填滿的二叉樹，有可能的例外是在底層，底層上的元素從左到右填入。這樣的樹稱為完全二叉樹（complete binary tree）。因為完全二叉樹很有規律，所以它可以用一個數組表示而不需要指針。對於數組任意位置 i 上的元素，其左兒子在位置 2i 上，右兒子在左兒子後的單元 2i+1 上，它的父親則在位置 lfloor i/2 rfloor 上。因此，不僅指針這裡不需要，而且遍歷該樹所需要的操作也極簡單，在大部分電腦上運行很可能非常快。

一個堆數據結構由一個數組，一個代表最大值的整數以及當前的堆大小組成。

優先隊列聲明：

#ifndef _BinHeap_H    struct HeapStruct;  typedef struct HeapStruct *PriorityQueue;    PriorityQueue Initialize(int MaxElements);  void Destroy(PriorityQueue H);  void MakeEmpty(PriorityQueue H);  void Insert(ElementType X, PriorityQueue H);  ElementType DeleteMin(PriorityQueue H);  ElementType FindMin(PriorityQueue H);  int IsEmpty(PriorityQueue H);  int IsFull(PriorityQueue H);    #endif    struct HeapStruct  {      int Capacity;      int Size;      ElementType *Elements;  }

4.4.2 堆序性質

使操作被快速執行的性質是堆序(heap order)性。由於我們想要快速地找出最小元，因此，最小元應該在根上。如果我們考慮任意子樹也應該是一個堆，那麼任意節點就應該小於它的所有後裔。

PriorityQueue  Initialize(int MaxElements)  {      PriorityQueue H;        if (MaxElements < MinPQSize)          Error("Priority queue size is too small");        H = malloc(sizeof(struct HeapStruct));      if (H == NULL)          FatalError("Out of space!!!");        H->Elements = malloc((MaxElements + 1)                           * sizeof(ElementType));        if (H->Elements == NULL)          FatalError("Out of space!!!");        H->Capacity =  MaxElements;      H->Size = 0;      H->Elements[0] = MinData;        return H;  }

根據堆序性質，最小元總是可以在根處找到。因此，我們以常數時間完成附加運算FinMin。

4.5 堆的基本操作

4.5.1 Insert (插入)

void  Insert(ElementType X, PriorityQueue H)  {      int i;        if (IsFull(H))      {          Error("Priority queue is full");          return;      }      for (i = ++H->Size; H->Elements[i / 2] > X; i /= 2)          H->Elements[i] = H->Elements[i / 2];      H->Elements[i] = X;  }

4.5.2 DeleteMin (刪除最小元)

ElementType  DeleteMin(PriorityQueue H)  {      int i, Child;      ElementType MinElement, LastElement;        if (IsEmpty(H))      {          Error("Priority queue is empty");          return H->Elements[0];      }      MinElement = H->Elements[1];      LastElement = H->Elements[H->Size--];        for(i = 1; i * 2 <= H->Size; i = Child)      {          Child = i * 2;          if (Child != H->size && H->Elements[Child + 1]                                < H->Elements[Child])              Child++;            if (LastElement > H->Elements[ Child ])              H->Elements[i] = H->Elements[Child];          else              break;      }      H->Elements[i] = LastElement;      return MinElement;  }

4.6 優先隊列的應用

作業系統設計：進程調度
圖論演算法
選擇問題：從N個元素中找出第k個最大的元素
事件模擬