今天是算法和數據結構的第21篇，我們來聊一個新的數據結構——堆(heap)。

和鍊表、二叉樹以及數組這些熱門的數據結構相比，堆相對比較冷門。如果你對數據結構了解不深的話，可能很少聽說。但是我們經常用到它，雖然可能你并不一定能感知到。比如說優先隊列，我們就經常使用。我們需要用到這樣一個數據結構，能夠根據我們存入數據的優先級進行排序，将優先級高的排在前面。在和調度相關的一些系統和算法當中，優先隊列是必然會用到的。但是很少有人知道，優先隊列說是一個隊列，但其實是通過堆實現的。

那麼堆究竟是一個怎樣的數據結構呢？

堆的實質其實是二叉樹，并且還不是一般的二叉樹，而是比較特别的二叉樹。

特别在什麼地方呢，在于這棵二叉樹除了葉子之外的所有節點都是“滿”的。所謂的滿，也就是沒有空缺的意思。

從上圖當中我們可以看到，如果去掉最後一層，那麼這棵二叉樹就是全滿的。最後一層葉子節點也是有要求的，要求葉子節點都靠左對齊。滿足這兩個條件的二叉樹成為完全二叉樹（complete binary tree）。這個概念如果記不住也沒有關系，我好像也隻在堆當中遇到。

堆是完全二叉樹，但是顯然不是所有的完全二叉樹都是堆，堆還有一個特殊的性質，就是大小的傳遞性。

堆根據大小傳遞性的不同分為大頂堆和小頂堆，所謂的大頂堆就是堆頂的元素也就是樹根的元素是最大的。如果是小頂堆則相反，堆頂元素是最小的。所以這兩者基本一樣，我們就以大頂堆舉例。這個傳遞性其實很好理解，其實隻有一條，就是所有節點的值大于它兩個孩子的值。也就是說從樹根到樹葉每一條路徑都是遞減的。

我們可以看下這張圖：

100有兩個孩子節點，19和36，100比19和36都大。19有兩個孩子17和3，19比它們都大。這應該是很好理解的，堆巧妙的點在哪裡呢，巧妙的點在于我們可以用數組來存儲這個結構，而不需要自己建樹。用數組存儲的方法也很簡單，我們給圖上的點标上下标，可以得到：

我們找下規律，可以發現對于一個樹上的一個節點，假設它在數組當中的下标是i的話。那麼它的左孩子的下标是i * 2 1， 它的右孩子下标為i * 2 2，它的父節點是(i - 1) // 2。

有了這個規律之後，我們隻要知道某個點的坐标，就可以知道它的父親和兩個孩子的坐标。這也是用數組來存儲堆非常巧妙和方便的點。

有了這個性質有什麼用呢？其實很有用，我們可以利用它非常方便地完成堆的維護。

想象一下，首先，往堆的末尾插入元素并不會破壞完全二叉樹這個性質。因為完全二叉樹的葉子節點是往左對齊的，我們插入元素必然也是在最左邊，所以不管我們插入的元素數值是多大，這都不會影響完全二叉樹這個性質。但是顯然，我們插入的數值大小會影響堆結構的正确性，比如如果我們插入9，插入的位置就不滿足大頂堆的性質了。

這個時候，為了維護堆的性質我們需要調整當中的數據。所以其實堆插入元素的過程就是一個調整順序的過程，那怎麼調整呢，其實很簡單，就是将我們插入的元素向上比較，如果它比它的父節點元素更大，那麼就将它和父節點進行交換，一直到它小于父節點或者是它稱為堆頂為止。

假如說，我們插入的元素不是9，而是105，那麼最後得到的結果應該是這樣的：

這個就是堆的插入過程，因為我們隻有插入的位置可能會導緻破壞堆結構，所以我們隻需要從插入的位置開始往上維護即可。其餘的位置并不會影響，并且對于整個這條鍊路上可能會被影響的節點而言，它們隻可能變大，不可能減小，因此也不會出現交換了之後有新的不滿足堆性質的情況産生。

由于這個插入的過程是自下而上的，因此整個過程也被稱為是向上更新。

我們來看下向上維護的代碼，隻有幾行，非常簡單：

defmaintain(self): #因為向上更新出現在插入元素之後，所以從最後一個位置開始維護 n=self._size-1 #cmp是自定義比較函數，用來自定義大頂堆還是小頂堆 whilen>0andself.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方法，很容易實現建堆的過程。

defpush(self,item): ifself._size_limitisnotNoneandself._size>self._size_limit: raiseIndexError('Heapisfull') #array_size是數組的長度 #由于允許彈出元素，所以會導緻數組的長度大于當前元素的數量的情況 ifself._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 defheapify(elements,min_or_max='min',compare_function=None): #初始化，min_or_max表示是大頂堆還是小頂堆，允許傳入自定義比較函數 heap=HeapQueue(min_or_max=min_or_max,compare_function=compare_function) foriinelements: heap.push(i) returnheap

堆和其他數據結構不同，它對于數據的查詢非常有限，隻允許查詢堆頂的元素。如果是大頂堆就是允許查詢最大元素，否則則是允許查詢最小元素。同樣，也隻允許删除堆頂的元素，由于删除堆頂的元素好像擠牙膏一樣将元素擠出去一樣，所以也稱為“彈出”（pop）。

隻是查詢很好理解，我們返回數組下标為0的元素即可，但是如果是彈出該怎麼辦呢？彈出了之後，不是堆頂元素就空缺了嗎？産生空缺了之後怎麼辦呢？

一種辦法是從根節點的孩子當中選擇一個作為替補頂上來，但是替補頂上之後又會産生新的空缺，這樣一調整可能完全二叉樹的性質就保不住了。所以隻有一個辦法，也很直觀，就是将末尾的元素拿出來作為替補放到堆頂。但是顯然末尾的元素不是最大的，所以這樣操作之後還需要調整。

怎麼調整呢？

當然是從堆頂開始将它和左右孩子進行比較，如果左右孩子當中存在比它大的，那麼就交換，将這個元素往下傳遞。比如下圖當中，我們彈出堆頂的元素100，根據算法的邏輯，我們會用末尾的7作為替補。

第一次我們将它和19與36進行比較，由于要滿足大頂堆的性質，我們選擇其中最大的36交換。于是我們将7往下傳遞到了原來36的位置，我們繼續将它和兩個孩子節點進行比較。我們發現25大于7，于是我們繼續交換，這個時候到達了葉子節點，停止。

我們再反觀維護之後的結果，仍然滿足大頂堆的性質，并且仍然是一棵完全二叉樹。和剛才插入時候的維護進行對比，我們會發現其實這整個過程是一個向下更新的過程。堆這個數據結構的核心其實就在這兩個更新當中，在插入的時候向上更新，在彈出的時候向下更新。

代碼也非常簡單：

defpop(self): front=self.items[0] #彈出下标為0的節點之後，将末尾元素插入頭部 self.items[0]=self.items[self._size-1] self._size-=1 self.downward_maintain() returnfront defdownward_maintain(self): n=0 whilen*2 1<self._size: #計算左右孩子的下标 left_child=n*2 1 right_child=n*2 2 #判斷左右孩子的大小關系，隻會和其中大的發生交換 ifself.cmp(self.items[left_child],self.items[right_child]): #如果左孩子大于右孩子也大于父節點，則交換 ifself.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 #如果右孩子最大，也交換 elifself.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當中為我們封裝了現成的堆，我們隻需要調用它，就可以很輕松地自己封裝一個優先隊列。

importheapq classPriorityQueue: def__init__(self): self._queue=[] self._index=0 defpush(self,item,priority): #傳入兩個參數，一個是存放元素的數組，另一個是要存儲的元素，這裡是一個元組。 #由于heap内部默認由小到大排，所以對priority取負數 heapq.heappush(self._queue,(-priority,self._index,item)) self._index =1 defpop(self): returnheapq.heappop(self._queue)[-1]

如果你願意，你還可以往這個類當中加入一些其他的輔助函數。當然，我還是建議大家，都能自己從頭用堆實現一個屬于自己的優先隊列，體會一下親手實現數據結構的成就感。

堆很實用，也不難寫，希望大家都能體會到手撸數據結構的快樂。

今天的文章就到這裡，原創不易，求個關注。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!