堆和优先队列

1. 堆及其性质

采用树形结构的实现的优先队列的一种技术称之为(heap)。
从结构上看堆就是节点里存储数据的完全二叉树,但是堆中数据存储要满足一种特殊的堆序:
任意一个节点里面所存的数据先于或者等于其子节点里面的数据

  • 如果要求的是小元素优先,构造出来的堆就是小顶堆(小的元素在上),堆中每个节点的数据都小于或等于其子节点的数据。
  • 如果要求的是大元素优先,构造出来的堆就是大顶堆(大的元素在上),堆中每个节点的数据都大于或等于其子节点的数据,堆顶是最大的数据。

注意:
一般使用列表(或者数组来)来表示堆,元素索引从0开始:
节点N的索引位置为i,那么该节点的父节点的位置为 (i - 1) // 2

2. 优先队列的堆实现

解决堆的元素插入和删除的关键操作称之为筛选,筛选分为向上筛选向下筛选

2.1 插入元素和向上筛选

堆得插入元素操作需要使用向上筛选来使得新插入的元素符合堆序,插入元素可以在O(logn)时间内完成。

向上筛选:

  • 将待插入的元素首先插入到二叉树的最下层最右边的新的叶节点位置
  • 比较插入元素和其父节点的大小,如果插入的元素小于父节点,则交换两个元素的位置
  • 重复上面的操作,不断向上进行比较,直到某个父节点小于新插入的元素的值,或者新插入的元素已经到达根节点为止

2.2 弹出元素和向下筛选

由于堆顶元素就是最优元素,应该弹出的元素就是它。但是弹出堆顶元素之后,剩下的元素已经不再是堆,因此需要使用向下筛选来使得剩下的元素满足堆序,其时间复杂度也是O(logn)。

向下筛选:

  • 弹出堆顶元素之后,将堆中的最后一个元素 e 放到堆顶
  • 然后比较堆顶元素 e 和两个左右子节点的大小,将三者的最小值作为父节点
  • 如果左子节点最小,则交换 e 与左子节点的元素(这样 e 元素就被下移了一层),这个左子节点又有以其为父节点的子树,然后重复进行相同的比较和交换步骤,直到元素 e 在某次比较中是三者中最小的那个,则说明当前已经满足堆序或者 e 已经到了最后一层,此时也满足堆序。

3. 基于堆得优先队列类

在这个类里面采用一个 list 来存储元素,在 list 的尾端插入元素,首段作为堆顶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class PrioQueue:
def __init__(self, elist = []):
# list(elist)对elist进行拷贝操作,使得内部的表脱离原来的表,避免共享
self._elems = list(elist)
if self._elems:
# 构造堆序
self.build_heap()

def is_empty(self):
return not self._elems

def peek(self):
# 取出元素但是不删除
if self.is_empty():
raise HeapPriQueueError('in pop')
return self._elems[0]

def enqueue(self, e):
# 尾端插入一个元素
self._elems.append(e)
self.sfitup(e, len(self._elems) - 1)

def siftup(self, e, last_index):
# 上筛选操作
elems = self._elems
i = last_index # 新添加元素的索引位置
j = (last_index - 1) // 2 # last_index位置元素的父节点

while i > 0 and e < elems[j]: # 如果需要插入的元素小于当前节点的父节点的值
elems[i] = elems[j] # 将父节点的值下移到其子节点中去
i, j = j, (j - 1) // 2 # 更新i为当前节点位置,j为新的当前节点的父节点位置

elems[i] = e

def dequeue(self):
# 首部弹出一个元素
if self.is_empty():
raise HeapPriQueueError('in pop')
elems = self._elems
e0 = elems[0] # 堆顶元素
e = elems.pop() # 将最后一个元素弹出作为新元素进行过比较之后,维持堆序
if len(elems) > 0:
self.siftdown(e, 0, len(elems))
return e0

def siftdown(self, e, begin, end):
# 下筛选操作
elems = self._elems
i = begin # 根节点位置
j = begin * 2 + 1 # i节点位置的左子节点
while j < end:
if j + 1 < end and elems[j] > elems[j + 1]:
j += 1 # 如果左节点大于右节点, 将j指向小的右节点
if e < elems[j]: # 如果插入元素e小于j位置的值,则为3者中最小的
break
# 能执行到这一步的话,说明j位置元素是三者中最小的,则将其上移到父结点位置
elems[i] = elems[j]
# 更新i为被上移为父结点的原来的j的位置,更新j为更新后i位置的左子结点
i, j = j, j * 2 + 1
# 或者位置i已经更新到叶结点位置,则将e赋给这个叶结点。
elems[i] = e

def build_heap(self):
end = len(self._elems)
# 从最下层最优非子叶节点开始进行上筛选操作,完成堆序的构建
for i in range(end // 2 - 1, -1, -1):
self.siftdown(self._elems[i], i, end)

3.1 基于堆的优先队列实现图示

下面演示如何实现将一个无序的列表元素构成符合堆序的结构(小顶堆),假设列表初始值为[5, 6, 8, 1, 2, 4, 9]

  1. 初始的堆结构图

初始堆结构图

  1. 开始找到第一个非叶子节点,进行向下筛选,紧接着,对其余的非叶子结点也依次进行向下筛选,操作完成后,这时得到的结构就是堆序了。

进行向下筛选1

进行向下筛选2

进行向下筛选3

进行向下筛选4

4. Python中的堆

Python中的heap模块中一共有六个函数,分别为:

函数 描述
heappush(heap, x) 向堆中添加元素
heappop(heap) 弹出堆中的最小的元素,并维持堆中剩余元素的结构
heapify(heap) 将列表转换成堆
heapreplace(heap, x) 弹出堆中的最小的元素,然后插入新的元素
nlargest(n, iter) 用来寻找任何迭代对象iter中的n个最大值
nsmallest(n, iter) 用来寻找任何迭代对象iter中的n个最小值

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from heapq import heappush, heappop, heapify, heapreplace, nlargest, nsmallest

heap = []

for i in range(3):
heappush(heap, i)

print(heap) # out: [0, 1, 2]
heappush(heap, 0.5)
print(heap) # out: [0, 0.5, 1, 2]

heappop(heap)
print(heap) # out: [0.5, 1, 2]

arr = [5, 8, 0, 4, 6, 7]
heapify(arr)
print(arr) # out: [0, 4, 5, 8, 6, 7]

heaprepalce(arr, 5.5)
print(arr) # out: [4, 5.5, 5, 8, 6, 7]

lst = [5, 8, 0, 4, 6, 7]
print(nlargest(3, lst)) # out: [8, 7, 6]
print(nsmallest(3, lst)) # out: [0, 4, 5]

5. Python中队列

Thread-Safe FIFO Implementation

5.1 基本FIFO队列

队列的基本实现是先进先出,元素从队列的一端使用put()函数进行添加,从另外一头使用get()函数进行删除元素。

1
2
3
4
5
6
7
8
9
10
11
12
import queue

que = queue.Queue()

for i in range(5):
que.put(i)

while not que.empty():
print(que.get(), end=' ')
print()

# out: 0, 1, 2, 3, 4

5.2 LIFO队列

使用栈的数据结构来实现后进先出的队列

1
2
3
4
5
6
7
8
9
10
11
12
import queue

que = queue.LifoQueue()

for i in range(5):
que.put(i)

while not que.empty():
print(que.get(), end=' ')
print()

# out: 4, 3, 2, 1, 0

5.3 优先队列

1
2
3
4
5
6
7
8
9
10
11
12
import queue

que = queue,PriorityQueue(3) # 优先级,优先级使用数字表示,数字越小优先级越高
que.put(10, 'a')
que.put(1, 'b')
que.put(100, 'c')

while not que.empty():
print(que.get(), end='')
print()

# out: 'b' 'a' 'c'