优先队列的堆实现

发表于   |   分类于

优先队列的堆实现

堆及其性质

  1. 采用树形结构实现优先队列的一种有效技术成为 堆，节点数据的存储满足堆序。
    • 从根到任何一个叶节点，节点数据优先级递减
    • 堆顶元素优先级最高，O(1)时间即可得到
    • 位于不同路径上的元素，这里不关心其顺序
  2. 几个重要性质
    • 在一个堆最后追加一个元素，依然是完全二叉树，但未必是堆
    • 去掉堆顶，两个子堆上堆序不变
    • 去掉堆顶的两个子堆加入根元素，未必是堆（堆序无法保证）
    • 去掉堆中最后的元素，不破坏堆序

代码

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
#!/usr/bin/env python
#_*_ coding:utf-8 _*_
class PrioQueueError(ValueError):
	pass
class PrioQueue():
	'''
	Implementing priority queues using heaps.
	'''
	def __init__(self,elist=[]):
		self._elems = list(elist)
		if elist:
			self.buildheap()
	def is_empty(self):
		return not self._elems
	def peek(self):
		if self.is_empty():
			raise PrioQueueError('Already in peek.')
		return self._elems[0]
	def enqueue(self,e):
		self._elems.append(None)
		self.siftup(e,len(self._elems)-1)
	def siftup(self,e,last):
		elems,i,j = self._elems,last,(last-1)//2
		while i > 0 and e < elems[j]:
			elems[i] = elems[j]
			i,j = j,(j-1)//2
		elems[i] = e
	def dequeue(self):
		if self.is_empty():
			raise PrioQueueError('Already in dequeue.')
		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,i,j = self._elems,begin,begin*2+1
		while j < end:
			if j+1 < end and elems[j+1] < elems[j]:
				j += 1
			if e < elems[j]:
				break
			elems[i] = elems[j]
			i,j = j, 2*j+1
		elems[i] = e
	def buildheap(self):
		end = len(self._elems)
		for i in range(end//2,-1,-1):
			self.siftdown(self._elems[i],i,end)

复杂度

操作 复杂度
创建操作 O(n)
插入和弹出元素 O(log n)
  • 程序出自《数据结构与算法Python语言描述》