「資料結構與演算法」通俗易懂講解 二叉堆

堆的應用場景

堆(heap)又被為優先佇列(priority queue)。儘管名為優先佇列，但堆並不是佇列。回憶一下，在佇列中，我們可以進行的限定操作是dequeue和enqueue。dequeue是按照進入佇列的先後順序來取出元素。而在堆中，

我們不是按照元素進入佇列的先後順序取出元素的，而是按照元素的優先順序取出元素。

這就好像候機的時候，無論誰先到達候機廳，總是頭等艙的乘客先登機，然後是商務艙的乘客，最後是經濟艙的乘客。每個乘客都有頭等艙、商務艙、經濟艙三種個鍵值(key)中的一個。頭等艙->商務艙->經濟艙依次享有從高到低的優先順序。

再比如，封建社會的等級制度，也是一個堆。在這個堆中，

國王、貴族、騎士和農民是從高到低的優先順序。

Linux內核中的調度器(scheduler)會按照各個進程的優先順序來安排CPU執行哪一個進程。電腦中通常有多個進程，每個進程有不同的優先順序(該優先順序的計算會綜合多個因素)。內核會找到優先順序最高的進程，

並執行。如果有優先順序更高的進程被提交，那麼調度器會轉而安排該進程運行。優先順序比較低的進程則會等待。“堆”是實現調度器的理想資料結構。C/C++的學習群496926338無論你是大牛還是小白，是想轉行還是想入行都可以來瞭解一起進步一起學習！群內有很多乾貨和技術分享！

堆的一個經典的實現是完全二叉樹(complete binary tree)。這樣實現的堆成為二叉堆(binary heap)。

二叉堆介紹

前面講了二叉堆是完全二元樹或者是近似完全二元樹實現的堆結構，

關於二叉樹，詳細介紹請見前面文章二叉搜尋樹（請戳我），二叉堆按照資料的排列方式可以分為兩種：最大堆和最小堆。

最大堆：父結點的鍵值總是大於或等於任何一個子節點的鍵值；如下圖左

最小堆：父結點的鍵值總是小於或等於任何一個子節點的鍵值。如下圖右

二叉堆定義及性質

二叉堆一般都通過"陣列"來實現。

陣列實現的二叉堆，父節點和子節點的位置存在一定的關係。有時候，我們將"二叉堆的第一個元素"放在陣列索引0的位置，有時候放在1的位置。當然，它們的本質一樣(都是二叉堆)，只是實現上稍微有一丁點區別。注意：本文二叉堆的實現統統都是採用"二叉堆第一個元素在陣列索引為0"的方式！

假設"第一個元素"在陣列中的索引為 0 ，對於父節點和子節點的位置有如下關係：

(1) 索引為i的左孩子的索引是 (2*i+1);

(2) 索引為i的左孩子的索引是 (2*i+2);

(3) 索引為i的父結點的索引是 floor((i-1)/2);

下面給出二叉堆的C++定義，為了通用性，定義成一個類範本：MaxHeap

template class MaxHeap{ private: T *mHeap; // 數據 int mCapacity; // 總的容量 int mSize; // 實際容量 private: // 最大堆的向下調整演算法 void filterdown(int start, int end); // 最大堆的向上調整演算法(從start開始向上直到0，調整堆) void filterup(int start); public: MaxHeap(); MaxHeap(int capacity); ~MaxHeap(); // 返回data在二叉堆中的索引 int getIndex(T data); // 刪除最大堆中的data int remove(T data); // 將data插入到二叉堆中 int insert(T data); // 列印二叉堆 void print();};

MaxHeap是最大堆的對應的類。它包括的核心內容是"添加"和"刪除"，理解這兩個演算法，二叉堆也就基本掌握了。下篇文章對它們進行介紹。C/C++的學習群496926338無論你是大牛還是小白，是想轉行還是想入行都可以來瞭解一起進步一起學習！群內有很多乾貨和技術分享！

它包括的核心內容是"添加"和"刪除"，理解這兩個演算法，二叉堆也就基本掌握了。下篇文章對它們進行介紹。C/C++的學習群496926338無論你是大牛還是小白，是想轉行還是想入行都可以來瞭解一起進步一起學習！群內有很多乾貨和技術分享！