喜歡我的文章，歡迎關注個人公衆号：數學程式設計
以前面試的時候碰到過問堆資料結構的，當時對資料結構了解太少，沒能回答上來，可能是以錯過了一次非常好的機會。從那以後一直在補基礎知識，今天就全面總結一下堆以及堆的應用。這裡你需要一些樹資料結構的基礎知識。
介紹資料結構-堆
把稻谷堆在地上就形成了堆，堆的結構非常清楚，上面小下面大，這樣的堆稱為小頂堆（又稱作最小堆）。最小堆在資料結構中是這樣定義的父節點的值恒小于等于子節點的值，此堆稱為最小堆，那麼大頂堆就是父節點的值恒大于等于子節點的值1。
堆是一種樹狀的資料結構，我們通常說的堆是一棵完全二叉樹結構。堆隻有兩種類型，就是上面提到的最小堆和最大堆，下面我們以最大堆作為案例來說明堆的存儲與操作。
堆的存儲與操作
下面是最大堆的例子，每個父節點都大于等于子節點的值。最大的值自然就是根節點了。
由于堆是一種非常特殊的二叉樹，而且還是完全二叉樹（上面的例子是滿二叉樹），那麼隻需要使用數組就能存儲整個樹結構了。根節點放在數組的第二個元素位置（下标為1），這樣的好處就是對于任意節點 i i i，左子節點就是 2 i 2i 2i，右子節點為 2 i + 1 2i+1 2i+1，父節點為 i / 2 i/2 i/2再地闆取整。
存儲的關鍵在于通路，通過上面這種方式解決了存儲和通路以後，接下來要看堆有哪些操作了。我們能夠想到的操作應該有：
- 插入一個新元素
- 擷取根節點元素
- 将序列堆化（變成堆）
圖文講解堆排序
其實堆的操作大緻也就這3種了。實際實作堆的過程中會更加細化這些操作。下面是參考wiki上的操作：
比如擷取堆頂的元素（根節點）。首先拿到根結點，然後從堆中删除根結點，接下來将剩餘的資料再次堆化。通過這些操作就完成了一次擷取對頂元素的值。
堆排序
上面介紹了一些關于堆的基礎知識，接下來就用堆進行排序了。把一個序列從小到大進行排序，實際上隻需要把這個序列變成最小堆，然後不斷的從最小堆中擷取根節點，就得到有序序列了。聽起來是不是覺得有點麻煩，但是實際的時間複雜度非常理想，是 o ( n log n ) o(n\log n) o(nlogn)。這得力于從堆化的資料中每次擷取根節點，然後再次堆化的時間複雜度是 o ( log n ) o(\log n) o(logn)，對于問題規模n來說，完成所有的操作算法複雜度自然就是 o ( n log n ) o(n\log n) o(nlogn)了。
總結
堆資料以及堆排序的用處非常大，尤其是對于一個動态的資料集（不斷添加新元素的資料集），每次擷取根節點就更加便捷了。同時堆也可以作為一種優先隊列（可以允許插隊的隊列），每次從對列中擷取優先級最高的元素作為優先處理的對象。這種情況很常見，比如在作業系統的資源排程過程中，作業系統通常會處理優先級高的程序，而這些程序存儲在優先隊列中。
本文暫時不貼出堆的實作代碼了，最麻煩的操作是删除堆頂以後再次堆化和插入新元素的堆化，實作兩種操作的思路差不多。删除堆頂以後把最後一個元素放在堆頂，然後逐漸與其子節點比較，這個過程叫向下篩選Sift Down（下沉）。而插入新元素，先放在最後，然後逐漸與父節點比較，這個過程叫向上篩選Sift Up（上浮）。還是挺簡單的。
- https://zh.wikipedia.org/wiki/%E5%A0%86%E7%A9%8D ↩︎