優(yōu)先隊(duì)列的二叉堆實(shí)現(xiàn)

在前面的章節(jié)里我們學(xué)習(xí)了“先進(jìn)先出”（ FIFO ）的數(shù)據(jù)結(jié)構(gòu)：隊(duì)列（ Queue ）。隊(duì)列有一種變體叫做“優(yōu)先隊(duì)列”（ Priority Queue ）。優(yōu)先隊(duì)列的出隊(duì)（ Dequeue ）操作和隊(duì)列一樣，都是從隊(duì)首出隊(duì)。但在優(yōu)先隊(duì)列的內(nèi)部，元素的次序卻是由“優(yōu)先級(jí)”來決定：高優(yōu)先級(jí)的元素排在隊(duì)首，而低優(yōu)先級(jí)的元素則排在后面。這樣，優(yōu)先隊(duì)列的入隊(duì)（ Enqueue ）操作就比較復(fù)雜，需要將元素根據(jù)優(yōu)先級(jí)盡量排到隊(duì)列前面。我們將會(huì)發(fā)現(xiàn)，對(duì)于下一節(jié)要學(xué)的圖算法中的優(yōu)先隊(duì)列是很有用的數(shù)據(jù)結(jié)構(gòu)。

我們很自然地會(huì)想到用排序算法和隊(duì)列的方法來實(shí)現(xiàn)優(yōu)先隊(duì)列。但是，在列表里插入一個(gè)元素的時(shí)間復(fù)雜度是 O(n) ，對(duì)列表進(jìn)行排序的時(shí)間復(fù)雜度是 O(nlogn) 。我們可以用別的方法來降低時(shí)間復(fù)雜度。一個(gè)實(shí)現(xiàn)優(yōu)先隊(duì)列的經(jīng)典方法便是采用二叉堆（ Binary Heap ）。二叉堆能將優(yōu)先隊(duì)列的入隊(duì)和出隊(duì)復(fù)雜度都保持在 O(logn) 。

二叉堆的有趣之處在于，其邏輯結(jié)構(gòu)上像二叉樹，卻是用非嵌套的列表來實(shí)現(xiàn)。二叉堆有兩種：鍵值總是最小的排在隊(duì)首稱為“最小堆（ min heap ）”，反之，鍵值總是最大的排在隊(duì)首稱為“最大堆（ max heap ）”。在這一節(jié)里我們使用最小堆。

二叉堆的操作

二叉堆的基本操作定義如下：

1. BinaryHeap() ：創(chuàng)建一個(gè)空的二叉堆對(duì)象
2. insert(k) ：將新元素加入到堆中
3. findMin() ：返回堆中的最小項(xiàng)，最小項(xiàng)仍保留在堆中
4. delMin() ：返回堆中的最小項(xiàng)，同時(shí)從堆中刪除
5. isEmpty() ：返回堆是否為空
6. size() ：返回堆中節(jié)點(diǎn)的個(gè)數(shù)
7. buildHeap(list) ：從一個(gè)包含節(jié)點(diǎn)的列表里創(chuàng)建新堆

下面所示代碼是二叉堆的示例?？梢钥吹綗o論我們以哪種順序把元素添加到堆里，每次都是移除最小的元素。我們接下來要來實(shí)現(xiàn)這個(gè)過程。

            
from pythonds.trees.binheap import BinHeap

bh = BinHeap()
bh.insert(5)
bh.insert(7)
bh.insert(3)
bh.insert(11)

print(bh.delMin())

print(bh.delMin())

print(bh.delMin())

print(bh.delMin())
          

為了更好地實(shí)現(xiàn)堆，我們采用二叉樹。我們必須始終保持二叉樹的“平衡”，就要使操作始終保持在對(duì)數(shù)數(shù)量級(jí)上。平衡的二叉樹根節(jié)點(diǎn)的左右子樹的子節(jié)點(diǎn)個(gè)數(shù)相同。在堆的實(shí)現(xiàn)中，我們采用“完全二叉樹”的結(jié)構(gòu)來近似地實(shí)現(xiàn)“平衡”。完全二叉樹，指每個(gè)內(nèi)部節(jié)點(diǎn)樹均達(dá)到最大值，除了最后一層可以只缺少右邊的若干節(jié)點(diǎn)。圖 1 所示是一個(gè)完全二叉樹。

圖 1：完全二叉樹

有意思的是我們用單個(gè)列表就能實(shí)現(xiàn)完全樹。我們不需要使用節(jié)點(diǎn)，引用或嵌套列表。因?yàn)閷?duì)于完全二叉樹，如果節(jié)點(diǎn)在列表中的下標(biāo)為 p，那么其左子節(jié)點(diǎn)下標(biāo)為 2p，右節(jié)點(diǎn)為 2p+1。當(dāng)我們要找任何節(jié)點(diǎn)的父節(jié)點(diǎn)時(shí)，可以直接使用 python 的整除。如果節(jié)點(diǎn)在列表中下標(biāo)為 n ，那么父節(jié)點(diǎn)下標(biāo)為 n//2 .圖 2 所示是一個(gè)完全二叉樹和樹的列表表示法。注意父節(jié)點(diǎn)與子節(jié)點(diǎn)之間 2p 與 2p+1 的關(guān)系。完全樹的列表表示法結(jié)合了完全二叉樹的特性，使我們能夠使用簡單的數(shù)學(xué)方法高效地遍歷一棵完全樹。這也使我們能高效實(shí)現(xiàn)二叉堆。

堆次序的性質(zhì)

我們?cè)诙牙飪?chǔ)存元素的方法依賴于堆的次序。所謂堆次序，是指堆中任何一個(gè)節(jié)點(diǎn) x，其父節(jié)點(diǎn) p 的鍵值均小于或等于 x 的鍵值。圖 2 所示是具備堆次序性質(zhì)的完全二叉樹。

圖 2：完全樹和它的列表表示法

二叉堆操作的實(shí)現(xiàn)

接下來我們來構(gòu)造二叉堆。因?yàn)榭梢圆捎靡粋€(gè)列表保存堆的數(shù)據(jù)，構(gòu)造函數(shù)只需要初始化一個(gè)列表和一個(gè) currentSize 來表示堆當(dāng)前的大小。Listing 1 所示的是構(gòu)造二叉堆的 python 代碼。注意到二叉堆的 heaplist 并沒有用到，但為了后面代碼可以方便地使用整除，我們?nèi)匀槐Ａ羲?

Listing 1

            
class BinHeap:
  def __init__(self):
    self.heapList = [0]
    self.currentSize = 0
          

我們接下來要實(shí)現(xiàn)的是 insert 方法。首先，為了滿足“完全二叉樹”的性質(zhì)，新鍵值應(yīng)該添加到列表的末尾。然而新鍵值簡單地添加在列表末尾，顯然無法滿足堆次序。但我們可以通過比較父節(jié)點(diǎn)和新加入的元素的方法來重新滿足堆次序。如果新加入的元素比父節(jié)點(diǎn)要小，可以與父節(jié)點(diǎn)互換位置。圖 3 所示的是一系列交換操作來使新加入元素“上浮”到正確的位置。

圖 3：新節(jié)點(diǎn)“上浮”到其正確位置

當(dāng)我們讓一個(gè)元素“上浮”時(shí)，我們要保證新節(jié)點(diǎn)與父節(jié)點(diǎn)以及其他兄弟節(jié)點(diǎn)之間的堆次序。當(dāng)然，如果新節(jié)點(diǎn)非常小，我們?nèi)匀恍枰獙⑺粨Q到其他層。事實(shí)上，我們需要不斷交換，直到到達(dá)樹的頂端。Listing 2 所示的是“上浮”方法，它把一個(gè)新節(jié)點(diǎn)“上浮”到其正確位置來滿足堆次序。這里很好地體現(xiàn)了我們之前在 headlist 中沒有用到的元素 0 的重要性。這樣只需要做簡單的整除，將當(dāng)前節(jié)點(diǎn)的下標(biāo)除以 2，我們就能計(jì)算出任何節(jié)點(diǎn)的父節(jié)點(diǎn)。

在Listing 3 中，我們已經(jīng)可以寫出 insert 方法的代碼。 insert 里面很大一部分工作是由 percUp 函數(shù)完成的。當(dāng)樹添加新節(jié)點(diǎn)時(shí)，調(diào)用 percUp 就可以將新節(jié)點(diǎn)放到正確的位置上。

Listing 2

            
def percUp(self,i):
  while i // 2 > 0:
   if self.heapList[i] < self.heapList[i // 2]:
     tmp = self.heapList[i // 2]
     self.heapList[i // 2] = self.heapList[i]
     self.heapList[i] = tmp
   i = i // 2
          

Listing 3

            
def insert(self,k):
  self.heapList.append(k)
  self.currentSize = self.currentSize + 1
  self.percUp(self.currentSize)
          

我們已經(jīng)寫好了 insert 方法，那再來看看 delMin 方法。堆次序要求根節(jié)點(diǎn)是樹中最小的元素，因此很容易找到最小項(xiàng)。比較困難的是移走根節(jié)點(diǎn)的元素后如何保持堆結(jié)構(gòu)和堆次序，我們可以分兩步走。首先，用最后一個(gè)節(jié)點(diǎn)來代替根節(jié)點(diǎn)。移走最后一個(gè)節(jié)點(diǎn)保持了堆結(jié)構(gòu)的性質(zhì)。這么簡單的替換，還是會(huì)破壞堆次序。那么第二步，將新節(jié)點(diǎn)“下沉”來恢復(fù)堆次序。圖 4 所示的是一系列交換操作來使新節(jié)點(diǎn)“下沉”到正確的位置。

圖 4：替換后的根節(jié)點(diǎn)下沉

為了保持堆次序，我們需將新的根節(jié)點(diǎn)沿著一條路徑“下沉”，直到比兩個(gè)子節(jié)點(diǎn)都小。在選擇下沉路徑時(shí)，如果新根節(jié)點(diǎn)比子節(jié)點(diǎn)大，那么選擇較小的子節(jié)點(diǎn)與之交換。Listing 4 所示的是新節(jié)點(diǎn)下沉所需的 percDown 和 minChild 方法的代碼。

Listing 4

            
def percDown(self,i):
  while (i * 2) <= self.currentSize:
    mc = self.minChild(i)
    if self.heapList[i] > self.heapList[mc]:
      tmp = self.heapList[i]
      self.heapList[i] = self.heapList[mc]
      self.heapList[mc] = tmp
    i = mc

def minChild(self,i):
  if i * 2 + 1 > self.currentSize:
    return i * 2
  else:
    if self.heapList[i*2] < self.heapList[i*2+1]:
      return i * 2
    else:
      return i * 2 + 1
          

Listing 5 所示的是 delMin 操作的代碼。可以看到比較麻煩的地方由一個(gè)輔助函數(shù)來處理，即 percDown 。

Listing 5

            
def delMin(self):
  retval = self.heapList[1]
  self.heapList[1] = self.heapList[self.currentSize]
  self.currentSize = self.currentSize - 1
  self.heapList.pop()
  self.percDown(1)
  return retval
          

關(guān)于二叉堆的最后一部分便是找到從無序列表生成一個(gè)“堆”的方法。我們首先想到的是，將無序列表中的每個(gè)元素依次插入到堆中。對(duì)于一個(gè)排好序的列表，我們可以用二分搜索找到合適的位置，然后在下一個(gè)位置插入這個(gè)鍵值到堆中，時(shí)間復(fù)雜度為 O(logn) 。另外插入一個(gè)元素到列表中需要將列表的一些其他元素移動(dòng)，為新節(jié)點(diǎn)騰出位置，時(shí)間復(fù)雜度為 O(n) 。因此用 insert 方法的總開銷是 O(nlogn) 。其實(shí)我們能直接將整個(gè)列表生成堆，將總開銷控制在 O(n) 。Listing 6 所示的是生成堆的操作。

Listing 6

            
def buildHeap(self,alist):
  i = len(alist) // 2
  self.currentSize = len(alist)
  self.heapList = [0] + alist[:]
  while (i > 0):
    self.percDown(i)
    i = i - 1
          

圖 5：將列表[ 9, 6, 5, 2, 3]生成一個(gè)二叉堆

圖 5 所示的是利用 buildHeap 方法將最開始的樹 [ 9, 6, 5, 2, 3] 中的節(jié)點(diǎn)移動(dòng)到正確的位置時(shí)所做的交換操作。盡管我們從樹中間開始，然后回溯到根節(jié)點(diǎn)，但 percDown 方法保證了最大子節(jié)點(diǎn)總是“下沉”。因?yàn)槎咽峭耆鏄洌魏卧谥虚g的節(jié)點(diǎn)都是葉節(jié)點(diǎn)，因此沒有子節(jié)點(diǎn)。注意，當(dāng) i=1 時(shí)，我們從根節(jié)點(diǎn)開始下沉，這就需要進(jìn)行大量的交換操作。可以看到，圖 5 最右邊的兩顆樹，首先 9 從根節(jié)點(diǎn)的位置移走，移到下一層級(jí)之后， percDown 進(jìn)一步檢查它此時(shí)的子節(jié)點(diǎn)，保證它下降到不能再下降為止，即下降到正確的位置。然后進(jìn)行第二次交換，9 和 3 的交換。由于 9 已經(jīng)移到了樹最底層的層級(jí)，便無法進(jìn)一步交換了。比較一下列表表示法和圖 5 所示的樹表示法進(jìn)行的一系列交換還是很有幫助的。

            
i = 2 [0, 9, 5, 6, 2, 3]
i = 1 [0, 9, 2, 6, 5, 3]
i = 0 [0, 2, 3, 6, 5, 9]
          

下列所示的代碼是完全二叉堆的實(shí)現(xiàn)。

            
def insert(self,k):
   self.heapList.append(k)
   self.currentSize = self.currentSize + 1
   self.percUp(self.currentSize)

  def percDown(self,i):
   while (i * 2) <= self.currentSize:
     mc = self.minChild(i)
     if self.heapList[i] > self.heapList[mc]:
       tmp = self.heapList[i]
       self.heapList[i] = self.heapList[mc]
       self.heapList[mc] = tmp
     i = mc

  def minChild(self,i):
   if i * 2 + 1 > self.currentSize:
     return i * 2
   else:
     if self.heapList[i*2] < self.heapList[i*2+1]:
       return i * 2
     else:
       return i * 2 + 1

  def delMin(self):
   retval = self.heapList[1]
   self.heapList[1] = self.heapList[self.currentSize]
   self.currentSize = self.currentSize - 1
          

能在 O(n) 的開銷下能生成二叉堆看起來有點(diǎn)不可思議，其證明超出了本書的范圍。但是，要理解用 O(n) 的開銷能生成堆的關(guān)鍵是因?yàn)? logn 因子基于樹的高度。而對(duì)于 buildHeap 里的許多操作，樹的高度比 logn 要小。