文章目录
- 优先队列
-
- 优先队列的应用
- 优先队列的实现
- 堆
-
- 堆的 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=)