优先队列

**优先队列:**另一种重要的缓存结构,

基于对一类二叉树的认识,可以做出优先队列的高效实现.

一.概念

作为缓存结构,优先队列与栈和队列类似,可以将数据元素保存其中,可以访问和弹出,优先队列的特点是存入其中的每项数据都另外附有一个数值,表示这个项的优先程度,称为其优先级,优先队列应该保证,在任何时候访问或者弹出的,总是当时在这个结构里保存的所有元素值中优先级最高的,如果该元素不弹出,再次访问还将得到它. 在一些场景中,可能出现不同元素具有相同优先级的情况,如果不止一个元素的优先级最高,优先队列将保证访问或弹出的是它们中的一个,具体是哪个元素由内部实现确定.

抽象地看,需要缓存的是一个有序集S=(D,≤)的元素,这里的"≤"是集合D上的一个全序(非严格的),表示元素的优先关系,优先队列要求保证"最优先元素先出(先用)",具体集合和序由实际需要确定,统一集合上也可能有不同的序,在实现优先队列时,必须确定使用的具体序关系.

允许D中不同元素具有相同优先级的情况,也就是说,可能有不同的a,b∈D,对它们a≤b且b≤a,这时就说a和b优先级相同,在这种应用场景中,如果要求保证优先级相同的元素先进先出(希望优先队列同时具有队列的FIFO性质),那就只能趉效率较低的实现,如果只要求保证访问(或弹出)的总是当时存在的最优先元素中的一个,不要求一定是其中最早进入优先队列的元素,那么就存在效率更高的实现.

优先队列的操作

• 创建,判断空(还可以有清空内容,确定当前元素个数等)
• 插入元素,访问和删除优先队列里(当时最优先)的元素

二. 基于线性表的实现

由于连续表可以存储数据元素,显然有可能作为优先队列的实现基础,数据项在连续表里的存储顺序可用于表示数据之间的某种顺序关系,对于优先队列,这个顺序可用于表示优先级关系,对于优先队列,这个顺序可用于表示优先级关系.例如,让数据的存储位置按优先顺序排列.

按优先级顺序存储数据项是一种可能,但不必须,实际上存在着两种可能的实现方案:

1. 在存入数据时,保证表中元素是在按优先顺序排列(作为一种数据不变式), 任何时候都可以直接取到当时在表里最优先的元素,采用有组织的元素存放方式,存入元素的操作比较麻烦,效率可能较低,但访问和弹出时比较方便
2. 存入数据时采用最简单的方式(例如:对顺序表存入表尾端,对链接表存入表头), 需要取用时,通过检索找到最优先的元素.采用这种无组织的方式存放元素,把选择最优元素的工作推迟到访问/取出时,存入操作的效率高但是取用麻烦,如果需要多次访问同一个元素但不弹出,就应该采用其他技术,避免重复检索.当然,也可以在一次检索后记录最优先元素,再次使用时就可以直接使用了,这种技术还需要与元素弹出相互配合.

下面采用在加入新数据的时候就设法确定正确的插入位置,保证表元素始终按优先顺序排列,由于考虑采用采用连续表实现,为保证访问和弹出最优先数据项的操作能在O(1)时间内完成,最优先的项应该出现在表的尾端.

三. 基于list实现优先队列

采用连续表技术,应该用一个list对象存储数据,list对象能根据存储元素的实际需要自动扩大存储区,但也应该注意,任何时候都只能在合法范围内使用下标表达式,超范围赋值和取值是运行错误,会引发IndexError异常.因此,在需要插入新元素时,只能先设法确定正确插入位置,而后调用list的insert(或其它操作)做定位插入.

# 需要存储的元素用"≤"比较优先级,值较小的元素优先级更高

# 首先定义一个异常类,在优先队列类里使用
class PrioQueueError(ValueError):
    pass

# 将优先队列定义一个类
class PrioQue:
    def __init__(self, elist=[])
    	self._elems = list(elist)
        self._elems.sort(reverse=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("in top")
        return self._elems[-1]
    
    def dequeue(self):
        if self.is_empty():
            raise PrioQueueError("in top")
        return self._elems.pop()
           

注意上面的参数默认值,以可变对象作为默认值是一种危险动作,应特别注意.在这里用list转换,有两个作用:

• 首先对实参表(包括默认值空表)做一个拷贝,避免共享
• 使构造函数的实参可以是任何可迭代对象,例如迭代器或者元组等

对连续表实现的分析:

• 插入元素是O(n), 其他都是O(1). 即使插入时表的存储区满,需要换一块存储,操作效率的复杂度量级仍然是O(n)
• 另一种实现技术方案,插入元素是O(1), 检查和弹出队列中的最优先元素都是O(n)

无论采用怎样的具体实现技术,在插入元素和取出元素的操作中总有一种是具有线性复杂度的操作