本文始發于個人公衆号：TechFlow，原創不易，求個關注
今天是算法和資料結構的第21篇，我們來聊一個新的資料結構——堆(heap)。
和連結清單、二叉樹以及數組這些熱門的資料結構相比，堆相對比較冷門。如果你對資料結構了解不深的話，可能很少聽說。但是我們經常用到它，雖然可能你并不一定能感覺到。比如說優先隊列，我們就經常使用。我們需要用到這樣一個資料結構，能夠根據我們存入資料的優先級進行排序，将優先級高的排在前面。在和排程相關的一些系統和算法當中，優先隊列是必然會用到的。但是很少有人知道，優先隊列說是一個隊列，但其實是通過堆實作的。
那麼堆究竟是一個怎樣的資料結構呢？
堆的定義
堆的實質其實是二叉樹，并且還不是一般的二叉樹，而是比較特别的二叉樹。
特别在什麼地方呢，在于這棵二叉樹除了葉子之外的所有節點都是“滿”的。所謂的滿，也就是沒有空缺的意思。
從上圖當中我們可以看到，如果去掉最後一層，那麼這棵二叉樹就是全滿的。最後一層葉子節點也是有要求的，要求葉子節點都靠左對齊。滿足這兩個條件的二叉樹成為完全二叉樹（complete binary tree）。這個概念如果記不住也沒有關系，我好像也隻在堆當中遇到。
堆是完全二叉樹，但是顯然不是所有的完全二叉樹都是堆，堆還有一個特殊的性質，就是大小的傳遞性。
堆根據大小傳遞性的不同分為大頂堆和小頂堆，所謂的大頂堆就是堆頂的元素也就是樹根的元素是最大的。如果是小頂堆則相反，堆頂元素是最小的。是以這兩者基本一樣，我們就以大頂堆舉例。這個傳遞性其實很好了解，其實隻有一條，就是所有節點的值大于它兩個孩子的值。也就是說從樹根到樹葉每一條路徑都是遞減的。
我們可以看下這張圖：
img
100有兩個孩子節點，19和36，100比19和36都大。19有兩個孩子17和3，19比它們都大。這應該是很好了解的，堆巧妙的點在哪裡呢，巧妙的點在于我們可以用數組來存儲這個結構，而不需要自己建樹。用數組存儲的方法也很簡單，我們給圖上的點标上下标，可以得到：
image-20200520203331364
我們找下規律，可以發現對于一個樹上的一個節點，假設它在數組當中的下标是i的話。那麼它的左孩子的下标是i * 2 + 1， 它的右孩子下标為i * 2 + 2，它的父節點是(i - 1) // 2。
有了這個規律之後，我們隻要知道某個點的坐标，就可以知道它的父親和兩個孩子的坐标。這也是用數組來存儲堆非常巧妙和友善的點。
堆的插入
有了這個性質有什麼用呢？其實很有用，我們可以利用它非常友善地完成堆的維護。
想象一下，首先，往堆的末尾插入元素并不會破壞完全二叉樹這個性質。因為完全二叉樹的葉子節點是往左對齊的，我們插入元素必然也是在最左邊，是以不管我們插入的元素數值是多大，這都不會影響完全二叉樹這個性質。但是顯然，我們插入的數值大小會影響堆結構的正确性，比如如果我們插入9，插入的位置就不滿足大頂堆的性質了。
image-20200520203932970
這個時候，為了維護堆的性質我們需要調整當中的資料。是以其實堆插入元素的過程就是一個調整順序的過程，那怎麼調整呢，其實很簡單，就是将我們插入的元素向上比較，如果它比它的父節點元素更大，那麼就将它和父節點進行交換，一直到它小于父節點或者是它稱為堆頂為止。
假如說，我們插入的元素不是9，而是105，那麼最後得到的結果應該是這樣的：
image-20200520204847608
這個就是堆的插入過程，因為我們隻有插入的位置可能會導緻破壞堆結構，是以我們隻需要從插入的位置開始往上維護即可。其餘的位置并不會影響，并且對于整個這條鍊路上可能會被影響的節點而言，它們隻可能變大，不可能減小，是以也不會出現交換了之後有新的不滿足堆性質的情況産生。
由于這個插入的過程是自下而上的，是以整個過程也被稱為是向上更新。
我們來看下向上維護的代碼，隻有幾行，非常簡單：
def maintain(self):
# 因為向上更新出現在插入元素之後，是以從最後一個位置開始維護
n = self._size - 1
# cmp是自定義比較函數，用來自定義大頂堆還是小頂堆
while n > 0 and self.cmp(self.items[n], self.items[(n-1)//2]):
# 如果目前節點比父節點“大”，則交換
self.items[n], self.items[(n-1)//2] = self.items[(n-1)//2], self.items[n]
n = (n - 1) // 2
了解了堆的插入之後，那麼堆的建立也應該很好了解了。所謂建堆的過程，其實就是将元素一個一個插入堆當中的過程。
我們利用maintain方法，很容易實作建堆的過程。
def push(self, item):
if self._size_limit is not None and self._size > self._size_limit:
raise IndexError('Heap is full')
# array_size是數組的長度
# 由于允許彈出元素，是以會導緻數組的長度大于目前元素的數量的情況
if self._size < self.array_size:
self.items[self._size] = item
self._size += 1
# 如果數組長度等于元素數量，那麼append到數組末尾
else:
self.items.append(item)
self._size += 1
self.array_size += 1
# 調用maintain，維護堆性質
self.maintain()
@staticmethod
def heapify(elements, min_or_max='min', compare_function=None):
# 初始化， min_or_max表示是大頂堆還是小頂堆，允許傳入自定義比較函數
heap = HeapQueue(min_or_max=min_or_max, compare_function=compare_function)
for i in elements:
heap.push(i)
return heap
堆的查詢與彈出
堆和其他資料結構不同，它對于資料的查詢非常有限，隻允許查詢堆頂的元素。如果是大頂堆就是允許查詢最大元素，否則則是允許查詢最小元素。同樣，也隻允許删除堆頂的元素，由于删除堆頂的元素好像擠牙膏一樣将元素擠出去一樣，是以也稱為“彈出”（pop）。
隻是查詢很好了解，我們傳回數組下标為0的元素即可，但是如果是彈出該怎麼辦呢？彈出了之後，不是堆頂元素就空缺了嗎？産生空缺了之後怎麼辦呢？
一種辦法是從根節點的孩子當中選擇一個作為替補頂上來，但是替補頂上之後又會産生新的空缺，這樣一調整可能完全二叉樹的性質就保不住了。是以隻有一個辦法，也很直覺，就是将末尾的元素拿出來作為替補放到堆頂。但是顯然末尾的元素不是最大的，是以這樣操作之後還需要調整。
怎麼調整呢？
當然是從堆頂開始将它和左右孩子進行比較，如果左右孩子當中存在比它大的，那麼就交換，将這個元素往下傳遞。比如下圖當中，我們彈出堆頂的元素100，根據算法的邏輯，我們會用末尾的7作為替補。
image-20200520210941652
第一次我們将它和19與36進行比較，由于要滿足大頂堆的性質，我們選擇其中最大的36交換。于是我們将7往下傳遞到了原來36的位置，我們繼續将它和兩個孩子節點進行比較。我們發現25大于7，于是我們繼續交換，這個時候到達了葉子節點，停止。
我們再反觀維護之後的結果，仍然滿足大頂堆的性質，并且仍然是一棵完全二叉樹。和剛才插入時候的維護進行對比，我們會發現其實這整個過程是一個向下更新的過程。堆這個資料結構的核心其實就在這兩個更新當中，在插入的時候向上更新，在彈出的時候向下更新。
代碼也非常簡單：
def pop(self):
front = self.items[0]
# 彈出下标為0的節點之後，将末尾元素插入頭部
self.items[0] = self.items[self._size-1]
self._size -= 1
self.downward_maintain()
return front
def downward_maintain(self):
n = 0
while n * 2 + 1 < self._size:
# 計算左右孩子的下标
left_child = n * 2 + 1
right_child = n * 2 + 2
# 判斷左右孩子的大小關系，隻會和其中大的發生交換
if self.cmp(self.items[left_child], self.items[right_child]):
# 如果左孩子大于右孩子也大于父節點，則交換
if self.cmp(self.items[left_child], self.items[n]):
self.items[n], self.items[left_child] = self.items[left_child], self.items[n]
n = left_child
else:
break
# 如果右孩子最大，也交換
elif self.cmp(self.items[right_child], self.items[n]):
self.items[n], self.items[right_child] = self.items[right_child], self.items[n]
n = right_child
else:
break
堆與優先隊列
到這裡，整個堆的主體部分就實作完了。整個過程還是比較直覺的，并不複雜，隻要記住了兩個更新就足夠了。
了解了堆之後我們再來看優先隊列，我們使用優先隊列的時候，希望每次取出優先級最大的資料，然後當我們填入資料的時候，隊列會自動根據我們設定的優先級對資料進行排序。這不剛好就是堆的功能嗎？是以通過堆，我們可以很友善地實作優先隊列，當然我們沒有必要這麼做，因為在Python當中為我們封裝了現成的堆，我們隻需要調用它，就可以很輕松地自己封裝一個優先隊列。
import heapq
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
# 傳入兩個參數，一個是存放元素的數組，另一個是要存儲的元素，這裡是一個元組。
# 由于heap内部預設由小到大排，是以對priority取負數
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
如果你願意，你還可以往這個類當中加入一些其他的輔助函數。當然，我還是建議大家，都能自己從頭用堆實作一個屬于自己的優先隊列，體會一下親手實作資料結構的成就感。如果你想要參考我的代碼，可以在公衆号内回複“堆”，我把我的代碼發給你。
堆很實用，也不難寫，希望大家都能體會到手撸資料結構的快樂。
今天的文章就到這裡，原創不易，掃碼關注我，擷取更多精彩文章。