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

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

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

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

二叉堆的操作

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

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

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

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())

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

圖 1：完全二叉樹

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

堆次序的性質(zhì)

我們在堆里儲存元素的方法依賴于堆的次序。所謂堆次序，是指堆中任何一個節(jié)點 x，其父節(jié)點 p 的鍵值均小于或等于 x 的鍵值。圖 2 所示是具備堆次序性質(zhì)的完全二叉樹。

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

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

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

Listing 1

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

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

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

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

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

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é)點是樹中最小的元素，因此很容易找到最小項。比較困難的是移走根節(jié)點的元素后如何保持堆結(jié)構(gòu)和堆次序，我們可以分兩步走。首先，用最后一個節(jié)點來代替根節(jié)點。移走最后一個節(jié)點保持了堆結(jié)構(gòu)的性質(zhì)。這么簡單的替換，還是會破壞堆次序。那么第二步，將新節(jié)點“下沉”來恢復(fù)堆次序。圖 4 所示的是一系列交換操作來使新節(jié)點“下沉”到正確的位置。

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

為了保持堆次序，我們需將新的根節(jié)點沿著一條路徑“下沉”，直到比兩個子節(jié)點都小。在選擇下沉路徑時，如果新根節(jié)點比子節(jié)點大，那么選擇較小的子節(jié)點與之交換。Listing 4 所示的是新節(jié)點下沉所需的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操作的代碼。可以看到比較麻煩的地方由一個輔助函數(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)于二叉堆的最后一部分便是找到從無序列表生成一個“堆”的方法。我們首先想到的是，將無序列表中的每個元素依次插入到堆中。對于一個排好序的列表，我們可以用二分搜索找到合適的位置，然后在下一個位置插入這個鍵值到堆中，時間復(fù)雜度為O(logn)。另外插入一個元素到列表中需要將列表的一些其他元素移動，為新節(jié)點騰出位置，時間復(fù)雜度為O(n)。因此用insert方法的總開銷是O(nlogn)。其實我們能直接將整個列表生成堆，將總開銷控制在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]生成一個二叉堆

圖 5 所示的是利用buildHeap方法將最開始的樹[ 9, 6, 5, 2, 3]中的節(jié)點移動到正確的位置時所做的交換操作。盡管我們從樹中間開始，然后回溯到根節(jié)點，但percDown方法保證了最大子節(jié)點總是“下沉”。因為堆是完全二叉樹，任何在中間的節(jié)點都是葉節(jié)點，因此沒有子節(jié)點。注意，當(dāng)i=1時，我們從根節(jié)點開始下沉，這就需要進(jìn)行大量的交換操作?？梢钥吹?，圖 5 最右邊的兩顆樹，首先 9 從根節(jié)點的位置移走，移到下一層級之后，percDown進(jìn)一步檢查它此時的子節(jié)點，保證它下降到不能再下降為止，即下降到正確的位置。然后進(jìn)行第二次交換，9 和 3 的交換。由于 9 已經(jīng)移到了樹最底層的層級，便無法進(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]

下列所示的代碼是完全二叉堆的實現(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)的開銷下能生成二叉堆看起來有點不可思議，其證明超出了本書的范圍。但是，要理解用O(n)的開銷能生成堆的關(guān)鍵是因為logn因子基于樹的高度。而對于buildHeap里的許多操作，樹的高度比logn要小。

最新評論