医院网站建设计划,wordpress做游戏网站,酒店网络营销推广方式,东营市房产信息网最小索引优先队列(Min index priority queue)
在之前实现的最大优先队列和最小优先队列,他们可以分别快速访问到队列中最大元索和最小元素,但是他们有一 个缺点,就是没有办法通过索引访问已存在于优先队列中的对象,并更新它们。
为了实现这个目的,在优先队列的基础上,学习一种…最小索引优先队列(Min index priority queue)
在之前实现的最大优先队列和最小优先队列,他们可以分别快速访问到队列中最大元索和最小元素,但是他们有一 个缺点,就是没有办法通过索引访问已存在于优先队列中的对象,并更新它们。
为了实现这个目的,在优先队列的基础上,学习一种新的数据结构,索引优先队列。
接下来我们以最小索引优先队列举列最大优先索引队列有兴趣可以自行实现。
实现思路
实现功能的三个重要数组
数组items储存无序插入的元素的数组数组pq假设将items储存的元素进行从小到大排序并且items对应的原索引依旧保持不变而pq储存的元素就是items排序过后元素的原索引参照下图可更好地理解数组qpqp的元素对应pq中的索引 qp的索引对应pq中的元素也就对应着未排序的items中的元素与items元素的索引保持一致 这样删除时只需要根据传入的索引在qp中寻找对应的元素就可以跟快地找到了
实现的操作方法
size()获取队列的大小is_empty()判断队列是否为空less(x, y)对传入的两个索引对应当前队列的元素进行大小比较swap(i, j)对传入的两个索引对应当前队列中的元素进行值交换min_elem_index()获取最小元素的索引is_index_exist()判断索引在当前队列中是否对应一个元素insert(index, item)指定索引index处插入一个元素itemdelete_min_elem()删除最小元素并返回最小元素插入队列时的索引change_item(idx, itm)指定索引idx处将该处元素替换为itmswim()上浮排序操作同之前堆的排序中介绍sink()下沉排序操作同之前堆的排序中介绍
Python代码实现
import operatorclass IndexMinPriorityQueue:def __init__(self, length):self.items [None for _ in range(length)]# Ascendingly sort items and memorize the items relative index in itemsself.pq [None] [i if self.items[i] else None for i in range(len(self.items))]# Its index is associate with elements in pq, and also syncs with indices of list itemsself.qp [i if self.pq[i] else None for i in range(len(self.pq))]self.N 0def size(self):return self.Ndef is_empty(self):return self.N 0def less(self, i, j):Compare the given two items in self.itemsreturn operator.lt(self.items[self.pq[i]], self.items[self.pq[j]])def swap(self, i, j):But change the position of the two items in the subsidiary pq and qp listsself.pq[i], self.pq[j] self.pq[j], self.pq[i]self.qp[self.pq[i]], self.qp[self.pq[j]] i, jdef min_elem_index(self):Find the minimum elements indexreturn self.pq[1]def is_index_exist(self, index):Judge if the given index is exist in this queuereturn self.qp[index] is not Nonedef insert(self, index, item):Insert an element associated with the elements index in this queueif self.is_index_exist(index):returnself.items[index] itemself.N 1# Now it isnt a orderly queueself.pq[self.N] indexself.qp[index] self.N# swim the last element to make list pq orderedself.swim(self.N)def delete_min_elem(self):Delete the minimum element, and return its indexmin_index self.pq[1]# print(fmin_ele: {self.items[min_index]})self.swap(1, self.N)self.pq[self.N] Noneself.qp[min_index] Noneself.items[min_index] Noneself.N - 1self.sink(1)return min_indexdef change_item(self, idx, itm):Substitute a item which indexidx with a new item which valueitmself.items[idx] itmk self.qp[idx]self.sink(k)self.swim(k)def swim(self, index):Move the smaller element up; We should only change order in pq and qpwhile index 1:# Compare the current node with its parent node, if smaller, swim upif self.less(index, int(index/2)): # Compare values in itemsself.swap(index, int(index/2)) # But swap the mapping position in pq and qpindex int(index/2)def sink(self, index):Move the bigger element down; We should only change order in pq and qp# print(fSINK: idx:{index} N:{self.N})while 2*index self.N:index_smaller 2*index if 2*index1 self.N else \(2*index if self.less(2*index, 2*index1) else 2*index1)# print(findex_smaller: {index_smaller})# print(findex: {index})if self.less(index, index_smaller):breakself.swap(index, index_smaller)index index_smaller测试代码
if __name__ __main__:IMPQ IndexMinPriorityQueue(10)IMPQ.insert(0, C)IMPQ.insert(1, E)IMPQ.insert(2, A)print(fAfter three insert list items now is: {IMPQ.items})# print(fpq: {IMPQ.pq})# print(fqp: {IMPQ.qp})# print(fmin_elem_index: {IMPQ.min_elem_index()})index, item 0, BIMPQ.change_item(0, B)print(fChanged the item in index[{index}] to {item}, items now is {IMPQ.items})index, item 0, VIMPQ.change_item(0, V)print(fChanged the item in index[{index}] to {item}, items now is {IMPQ.items})while not IMPQ.is_empty():res IMPQ.delete_min_elem()print(fPop the minimum element: {res})print(fAfter delete all elements , its size: {IMPQ.size()})print(IMPQ.is_index_exist(0))测试结果
After three insert list items now is: [C, E, A, None, None, None, None, None, None, None]
Changed the item in index[0] to B, items now is [B, E, A, None, None, None, None, None, None, None]
Changed the item in index[0] to V, items now is [V, E, A, None, None, None, None, None, None, None]
Pop the minimum element: 2
Pop the minimum element: 1
Pop the minimum element: 0
After delete all elements , its size: 0
False这里为了测试结果直观直接将数组items拿出来了注意items中的元素是不会改变位置的实际改变的是用来定位items中元素的pq和qp数组
