《数据结构与算法Python语言描述》学习笔记chap6(3)优先队列

《数据结构与算法Python语言描述》学习笔记chap6(3)优先队列

20191201

优先队列

作为缓存结构&＃xff0c;优先队列与栈和队列类似&＃xff0c;可以将数据元素保存其中&＃xff0c;可以访问和弹出。
优先队列的特点是存入其中的每项数据都另外附有一个数值&＃xff0c;表示这个项的优先程度&＃xff0c;称为其优先级。优先队列应该保证&＃xff0c;在任何时候访问或弹出的&＃xff0c;总是当时在这个结构里保存的所有元素中优先级最高的。如果该元素不弹出&＃xff0c;再次访问还将得到他。

优先队列的线性表实现

基于线性表的实现
两种可能的实现方案&＃xff1a;
1&＃xff09;在存入数据时&＃xff0c;保证表中元素始终按优先顺序排列&＃xff1b;任何时候都可以直接取到当时在表里最优先元素。
采用有组织的元素存放方式&＃xff0c;存入元素的操作比较麻烦&＃xff0c;效率可能较低&＃xff0c;但访问和弹出比较方便&＃xff1b;
2&＃xff09;存入数据时采用最简单的方式&＃xff0c;需要用时&＃xff0c;通过检索找到最优先的元素。

基于list实现优先队列

# 优先队列:较小的优先级更高&＃xff0c;倒序排列&＃xff0c;队头是最小的元素
class PrioQueueError(ValueError):passclass PrioQue:def __init__(self,elist&＃61;[]):self._elems &＃61; list(elist)self._elems.sort(reverse&＃61;True) # 将参数从大到小排列def enqueue(self,e):"""插入到正确的位置"""i &＃61; len(self._elems) - 1while i >&＃61; 0:if self._elems[i] <&＃61; e:i -&＃61; 1else:breakself._elems.insert(i&＃43;1,e)def is_empty(self):return not self._elemsdef peek(self):if self.is_empty():raise PrioQueueError("in top")return self._elems[-1]def dequeue(self):if self.is_empty():raise PrioQueueError("in pop")return self._elems.pop()prique &＃61; PrioQue([3,7,4,8,1])
for i in range(0,3):prique.enqueue(i)
while not prique.is_empty():print(prique.dequeue())

运行结果&＃xff1a;
0
1
1
2
3
4
7
8

《数据结构与算法Python语言描述》学习笔记chap6(4&＃xff09;堆排序

20191206

优先队列的堆实现

堆及其性质
堆&＃xff1a;完全二叉树&＃xff0c;但数据要满足一种特殊的堆序&＃xff0c;
小顶堆&＃xff1a;队中最优先的元素位于二叉树的根节点&＃xff1b;
大顶堆&＃xff1a;每个结点的数据都大于或等于其子结点的数据&＃xff0c;堆顶是最大元素。

堆排序

def heap_sort(elems):def siftdown(elems,e,begin,end):"""将数据插入到合适的位置,作为主函数的内部函数"""i,j &＃61; begin,begin*2&＃43;1while j < end :if j &＃43;1 < end and elems[j&＃43;1] < elems[j]:j &＃43;&＃61; 1if e < elems[j]:breakelems[i] &＃61; elems[j]i , j &＃61; j,2*j&＃43;1elems[i] &＃61; eend &＃61; len(elems)# 构建小根堆for i in range(end//2,-1,-1):siftdown(elems,elems[i],i,end)# 依次取出最小的元素print(&＃39;依次取出最小的元素&＃39;)for i in range((end-1),0,-1):e &＃61; elems[i]elems[i] &＃61; elems[0]siftdown(elems,e,0,i) #调整结构print(elems[0])# end &＃61; 9
# for i in range(end//2,-1,-1):
# print(i,end &＃61; &＃39;&＃39;)
#
# print(&＃39;&＃39;)
# for i in range((end - 1), 0, -1):
# print(i,end &＃61; &＃39;&＃39;)elems &＃61; [1,6,8,0,3,5,2]
heap_sort(elems)


注&＃xff1a;
range(0,9,-1)
左闭右开&＃xff0c;-1表示倒序&＃xff0c;所以包含的范围是&＃xff1a;0-8
输出应为&＃xff1a;8&＃xff0c;7&＃xff0c;6&＃xff0c;5&＃xff0c;4&＃xff0c;3&＃xff0c;2&＃xff0c;1&＃xff0c;0