数据结构与算法(Python版)五十:优先队列和二叉堆
优先队列Priority Queue
前面我们学习了一种FIFO数据结构队列
队列有一种变体称为“优先队列”。
银行窗口取号排队, VIP客户可以插到队首,操作系统中执行关键任务的进程或用户特别指定,进程在调度队列中靠前
优先队列的出队跟队列一样从队首出队;
但在优先队列内部, 数据项的次序却是由“优先级”来确定:
高优先级的数据项排在队首,而低优先级的数据项则排在后面。这样,优先队列的入队操作就比较复杂,需要将数据项根据其优先级尽量挤到队列前方。
思考:有什么方案可以用来实现优先队列?
出队和入队的复杂度大概是多少?
二叉堆Binary Heap实现优先队列
实现优先队列的经典方案是采用二叉堆数据结构
二叉堆能够将优先队列的入队和出队复杂度都保持在O(log n)
二叉堆的有趣之处在于, 其逻辑结构上象二叉树, 却是用非嵌套的列表来实现的!
最小key排在队首的称为“最小堆min heap”
反之,最大key排在队首的是“最大堆max heap”
ADT BinaryHeap的操作定义如下:
- BinaryHeap():创建一个空二叉堆对象;
- insert(k):将新key加入到堆中;
- findMin():返回堆中的最小项,最小项仍保留在堆中;
- delMin():返回堆中的最小项,同时从堆中删除;
- isEmpty():返回堆是否为空;
- size():返回堆中key的个数;
- buildHeap(list):从一个key列表创建新堆
ADT BinaryHeap的操作示例
用非嵌套列表实现二叉堆
为了使堆操作能保持在对数水平上, 就必须采用二叉树结构;
同样, 如果要使操作始终保持在对数数量级上, 就必须始终保持二叉树的“平衡”
树根左右子树拥有相同数量的节点
我们采用“完全二叉树”的结构来近似实现“平衡”
完全二叉树,叶节点最多只出现在最底层和次底层,而且最底层的叶节点都连续集中在最左边,每个内部节点都有两个子节点, 最多可有1个节点例外
完全二叉树的列表实现及性质
完全二叉树由于其特殊性, 可以用非嵌套列表, 以简单的方式实现, 具有很好性质
如果节点的下标为p,那么其左子节点下标为2p,右子节点为2p+1,其父节点下标为p//2
堆次序Heap Order
任何一个节点x, 其父节点p中的key均小于x中的key
这样,符合“堆”性质的二叉树,其中任何一条路径,均是一个已排序数列, 根节点的key最小