优先队列的连续列表实现

发表于   |   分类于

优先队列的连续列表实现

两种实现方案

  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
#!/usr/bin/env python
#_*_ coding:utf-8 _*_
class PrioQueueError(ValueError):
	pass
class PrioQue():
	def __init__(self,elist=[]):
		self._elems = list(elist)           #使用list转换：对实参拷贝防止共享；实参可以是任一迭代对象
		self._elems = sort(reversed=True)	  #设置为较小的优先级高
	def enqueue(self,e):
		i = len(self._elems) - 1
		while i >= 0:                       #优先级相同的元素先进先出
			if self._elems[i] <= e:
				i -= 1
			else:
				break
		self._elems.insert(i+1,e)
	def is_empty(self):
		return not self._elems
	def peek(self):
		if self.is_empty():
			raise PrioQueueError('Already in top.')
		return self._elems[-1]
	def dequeue(self):
		if self.is_empty():
			raise PrioQueueError('No elem to pop.')
		return self._elems.pop()

操作效率（复杂度）

方案1

操作 复杂度
插入元素 O(n)
其他 O(1)

方案2

操作 复杂度
插入元素 O(1)，替换表存储空间需要O(n)时间
其他 O(n)
  • 程序出自 《数据结构与算法Python语言描述》