文章目錄
- 優先隊列
-
- 優先隊列的應用
- 優先隊列的實作
- 堆
-
- 堆的 python 實作
-
- 堆中節點的索引
- 查找元素
- 查找最小值
- 查找最小 K 個元素
- 查找最大值
- 删除最小值
- 删除任意元素
- 插入元素
- 堆的初始化
- 堆排序
- 構造堆的時間複雜度為 O(n)
優先隊列
優先隊列的基本操作：
- 插入元素
- 删除最小（大）元素
- 擷取最小（大）元素
實作了這三個需求的抽象資料類型就叫優先隊列
優先隊列的應用
- 資料壓縮——huffman 編碼
- 最短路徑——dijkstra 算法
- 最小生成樹——prim 算法
- 查找最小 k 個元素
優先隊列的實作
其實大家都知道優先隊列一般是用“堆”實作的，但原則上這不是必須的，下面看看用各種方法實作優先隊列時的工作效率:
| 實作方法 | 插入 | 删除最小 | 查找最小 |
|---|---|---|---|
| 無序數組 | 1 | n | n |
| 無序連結清單 | 1 | n | n |
| 有序數組 | n | 1 | 1 |
| 有序連結清單 | n | 1 | 1 |
| 二叉搜尋樹 | logn | logn | logn |
| 平衡二叉搜尋樹 | logn | logn | logn |
| 二叉堆 | logn | logn | 1 |
現在你知道為什麼要用堆來實作優先隊列了吧
堆
從結構來看，堆是完全二叉樹
從節點來看，堆中的父節點的值必須不大于（不小于）其子節點的值
一般也叫做最小堆（最大堆）
堆的 python 實作
以下是最小堆的實作
堆中節點的索引
class Heap:
def __init__(self, l=[]):
self.heapList = [None]+l # Elements in Heap
self.buildHeap()
@property
def size(self):
return len(self.heapList) - 1
def parent(self, index):
return index // 2
def leftChildIndex(self, index):
return 2 * index
def rightChildIndex(self, index):
return 2 * index + 1
def validIndex(self, index):
return index <= self.size and index >= 1
def hasChild(self, index):
return self.validIndex(index*2)
def leftChild(self, index):
lindex = self.leftChildIndex(index)
return self.heapList[lindex] if self.validIndex(lindex) else None
def rightChild(self, index):
rindex = self.rightChildIndex(index)
return self.heapList[rindex] if self.validIndex(rindex) else None
def minimumChild(self, i):
if not self.hasChild(i):
return None
elif not self.validIndex(self.rightChildIndex(i)):
return self.leftChildIndex(i)
lindex = self.leftChildIndex(i)
rindex = self.rightChildIndex(i)
return lindex if self.heapList[lindex] < self.heapList[rindex] else rindex
def __repr__(self):
return str(self.heapList[1:])
首先從上面的代碼可以發現在完全二叉樹中索引父節點和子節點非常容易！
下面來看一些常用操作：
查找元素
這個對于堆來說沒有優勢，隻能周遊
def searchElement(self, itm):
i = 1
while (self.validIndex(i)):
if itm == self.heapList[i]:
return i
i += 1
return None
查找最小值
直接傳回根節點，需要 O ( log ( 1 ) ) O(\log(1)) O(log(1))時間
def getMinimum(self):
return None if self.size == 0 else self.heapList[1]
查找最小 K 個元素
使用另一個堆來儲存臨時結果，時間複雜度為 O ( K log K ) O(K\log K) O(KlogK)
def topK(self, k):
assert(k >= 0 and k <= self.size)
result = []
HAux = Heap()
item = self.getMinimum()
HAux.insert(item)
while (len(result) < k):
item = HAux.deleteMin()
result.append(item)
if self.rightChild(self.searchElement(item)) is not None:
HAux.insert(self.rightChild(self.searchElement(item)))
if self.leftChild(self.searchElement(item)) is not None:
HAux.insert(self.leftChild(self.searchElement(item)))
return result
查找最大值
從最小堆裡找最大值，隻要周遊葉子節點即可， O ( n 2 ) = O ( n ) O(\frac{n}{2})=O(n) O(2n)=O(n)
def getMaximum(self):
maximum = self.heapList[self.parent(self.size)]
for i in range(self.parent(self.size)+1, self.size+1):
if self.heapList[i] > maximum:
maximum = self.heapList[i]
return maximum
删除最小值
删除根節點後需要從上之下調整一遍：percolateDown，需要 O ( log ( n ) ) O(\log(n)) O(log(n))時間
def swap(self, a, b):
self.heapList[a], self.heapList[b] = self.heapList[b], self.heapList[a]
def percolateDown(self, i):
while self.hasChild(i):
minimumChild = self.minimumChild(i)
if self.heapList[i] > self.heapList[minimumChild]:
self.swap(i, minimumChild)
i = minimumChild
def deleteMin(self):
retval = self.heapList[1]
self.swap(1, self.size)
self.heapList.pop()
self.percolateDown(1)
return retval
删除任意元素
和删除最小值相比，删除其他元素的前提是先從堆中找到該元素，這需要 O ( n ) O(n) O(n) 時間，然後将該元素和末端的葉子節點交換，删除末端節點，然後從被删除節點的原始位置開始調整堆。
def delete(self, key):
loc = self.searchElement(key)
if loc is not None:
self.swap(loc, self.size)
self.heapList.pop()
self.percolateDown(loc)
插入元素
一般直接插入末尾，然後從下至上調整堆 percolateUp，需要 O ( l o g n ) O(logn) O(logn)時間
def percolateUp(self, i):
while self.validIndex(i // 2):
if self.heapList[i] < self.heapList[i // 2]:
self.swap(i, i//2)
i = i // 2
def insert(self, k):
self.heapList.append(k)
self.percolateUp(self.size)
堆的初始化
從數組構造堆，圖示可見《堆排序建立初始堆》
def buildHeap(self):
n = self.size
for i in range(self.parent(n), 0, -1):
self.heapify(i)
def heapify(self, index):
left = self.leftChildIndex(index)
right = self.rightChildIndex(index)
minimum = index
if self.validIndex(left) and self.heapList[left] < self.heapList[index]:
minimum = left
if self.validIndex(right) and self.heapList[right] < self.heapList[minimum]:
minimum = right
if minimum != index:
self.swap(minimum, index)
self.heapify(minimum)
堆排序
def heapSort(self):
result = []
while self.size > 0:
result.append(self.deleteMin())
return result
構造堆的時間複雜度為 O(n)
證明：
- 調整堆的順序是從下至上，從右往左，從最後一個非葉子節點開始進行 heapify 操作
- 從一個節點開始進行 heapify 操作的複雜度等于該節點的高度，即從該節點向下到最遠的葉子節點的路徑的長度
- 是以構造堆的時間複雜度 T ( n ) T(n) T(n) 等于所有非葉子節點的高度之和
-
不妨設堆的高度為 h ≃ l o g 2 ( n ) h \simeq log_2(n) h≃log2(n)，則 T ( n ) = h + 2 ( h − 1 ) + 2 2 ( h − 2 ) + ⋯ + 2 h − 1 T(n) = h + 2(h-1) + 2^2(h-2) + \cdots + 2^{h-1} T(n)=h+2(h−1)+22(h−2)+⋯+2h−1 = ∑ i = 1 h − 1 2 i ( h − i ) = \sum_{i=1}^{h-1} 2^i (h-i) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ =i=1∑h−12i(h−i)
如此一來，變成一個聯考常見的數列求和問題： 2 T ( n ) = ∑ i = 1 h − 1 2 i + 1 ( h − i ) = ∑ j = 2 h 2 j ( h − j + 1 ) 2T(n) = \sum_{i=1}^{h-1} 2^{i+1} (h-i) = \sum_{j=2}^{h} 2^j (h-j+1) 2T(n)=i=1∑h−12i+1(h−i)=j=2∑h2j(h−j+1) T ( n ) = 2 T ( n ) − T ( n ) = ∑ i = 2 h 2 i ( h − i + 1 ) − ∑ i = 1 h − 1 2 i ( h − i ) T(n) = 2T(n)-T(n) = \sum_{i=2}^{h} 2^i (h-i+1) -\sum_{i=1}^{h-1} 2^i (h-i) T(n)=2T(n)−T(n)=i=2∑h2i(h−i+1)−i=1∑h−12i(h−i) = 2 h + ∑ i = 2 h − 1 2 i − 2 ( h − 1 ) =2^h+\sum_{i=2}^{h-1} 2^i -2(h-1) =2h+i=2∑h−12i−2(h−1) = O ( 2 h ) = O(2^h) =O(2h) = O ( n ) =O(n) =O(n)
![筆試面試題目：滑動視窗(二)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)