网站建设北京,一个网站开发的假设,莱西网站建设哪家好,135编辑器优先队列(Priority queue)的介绍
优先队列是计算机中一种抽象的数据结构类#xff0c;它有着一个类似和队列或者堆的结构#xff0c;但是其中每个元素额外有一个优先级别在一个优先队列中#xff0c;一个高优先顺序的元素会先执行与低优先顺序的元素。在它的执行过程中它有着一个类似和队列或者堆的结构但是其中每个元素额外有一个优先级别在一个优先队列中一个高优先顺序的元素会先执行与低优先顺序的元素。在它的执行过程中如果两个元素拥有相同的优先顺序则会根据他们进入队列的先后顺序来确定执行先后但是在在其他类型的数据结构中如果两个元素优先级别相同则不会定义这两个元素的先后执行顺序优先队列一般使用堆来进行实现但他们在概念上与堆是有区别的。一个优先队列它可以是一个“列表”也可以是一个“字典”正如一个列表可以使用链表或者数组来实现一样优先队列可以用堆或者其他各种不同的方法如无序数组来实现
要实现的两种优先队列
两种优先队列
最大优先队列(Max priority queue)最大优先级的元素在队列最前面可以指定最大元素取出和删除最小优先队列(Max priority queue)最小优先级的元素在队列最前面可以指定最小元素取出和删除
使用堆(数组)实现最大优先队列
定义方法
size()获取队列大小less(x, y)对传入的两个索引对应当前队列的元素进行大小比较is_empty()判断队列是否为空swap(i, j)对传入的两个索引对应当前队列中的元素进行值交换append(item)在队列末尾添加指定元素extract_max()取出并删除最大优先级的元素sink()使用下沉排序操作对删除元素后的队列进行排序swim()使用上浮排序操作对从尾部插入元素的队列进行排序
最大优先队列Python代码实现
class MaxPriorityQueue:def __init__(self):self.heap [None]self.N 0def size(self):return self.Ndef less(self, i, j):return self.heap[i] self.heap[j]def is_empty(self):return self.N 0def swap(self, i, j):self.heap[i], self.heap[j] self.heap[j], self.heap[i]def append(self, item):self.heap.append(item)self.N 1self.swim(self.N)def extract_max(self):if self.N 1:returnfirst self.heap[1]# print(ffirst: {first})self.swap(1, self.N)del self.heap[self.N]self.N - 1self.sink(1, self.N)return firstdef sink(self, index, _range):while 2*index _range:max_index 2*index if 2*index1 _range else \(2*index1 if self.less(2*index, 2*index1) else 2*index)if self.less(max_index, index):breakself.swap(max_index, index)index max_indexdef swim(self, index):while index 1:if self.less(int(index/2), index):self.swap(int(index/2), index)index int(index/2)if __name__ __main__:MPQ MaxPriorityQueue()MPQ.append(A)MPQ.append(B)MPQ.append(C)MPQ.append(D)MPQ.append(E)MPQ.append(F)MPQ.append(G)while not MPQ.is_empty():_max MPQ.extract_max()print(_max, end )Max Priority Queue运行测试结果
G F E D C B A 进行尾部插入元素操作时从小到大附加到队列依次抽离最大元素是从大到小返回结果
使用堆(数组)实现最小优先队列
核心方法与最大优先队列实习的实现是差不多的只是在父结点与子结点排序比较时将两者位置调换再进行比较和位置移动操作
最小优先队列Python代码实现
import operatorclass MinPriorityQueue:def __init__(self):self.heap [None]self.N 0def size(self):return self.Ndef is_empty(self):return self.N 0def less(self, i, j):return operator.lt(self.heap[i], self.heap[j])def swap(self, i, j):self.heap[i], self.heap[j] self.heap[j], self.heap[i]def append(self, item):self.heap.append(item)self.N 1self.swim(self.N)def extract_min(self):if self.N 1:return_min self.heap[1]self.swap(1, self.N)del self.heap[self.N]self.N - 1self.sink(1, self.N)return _mindef swim(self, index):while index 1:if self.less(index, int(index / 2)):self.swap(index, int(index / 2))index int(index / 2)def sink(self, index, _range):while 2 * index _range:min_index 2 * index if 2 * index 1 _range else \(2 * index if self.less(2 * index, 2 * index 1) else 2 * index 1)if self.less(index, min_index):breakself.swap(index, min_index)index min_indexif __name__ __main__:MPQ MinPriorityQueue()MPQ.append(G)MPQ.append(F)MPQ.append(E)MPQ.append(D)MPQ.append(C)MPQ.append(B)MPQ.append(A)while not MPQ.is_empty():_min MPQ.extract_min()print(_min, end )Min Priority Queue运行测试结果
A B C D E F G
