优先队列(堆)

优先队列(priority queue)
普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。

模型

优先队列允许至少两种操作的数据结构:insert和deleteMin(删除最小者),它是找出、返回并删除优先队列中最小的元素。
insert等价于入队,deleteMin等价出队。

二叉堆

结构性质

二叉堆是一种特殊的堆,二叉堆是完全填满的二元树(二叉树)或者是近似完全填满的二元树(二叉树)。二叉堆有两种:最大堆和最小堆。最大堆:父结点的键值总是大于或等于任何一个子节点的键值;最小堆:父结点的键值总是小于或等于任何一个子节点的键值。

因为完全二叉树很有规律,所以它可以用一个数组标识而不需要使用链。
后面始终把堆画成树,具体实现将使用简单的数组

一个堆结构将由一个(comparable对象的)数组和一个代表当前堆大小的整数组成。

堆序性质

让操作快速执行的性质是堆序性质(heap-order property)。
由于想要快速找出最小元素,因此最小元素应该在根上。

因此以常数时间得到附加操作findMin。

基本的堆操作

所有的工作都需要保证始终保持堆序性质。

insert操作

为将一个元素X插入到堆中,在下一个可用位置创建一个空穴,如果X可以放在该空穴中而并不破坏堆的序,那么插入完成。否则,把空穴的父节点上的元素移入该空穴中,这样,空穴就朝着跟的方向向上冒一步,继续该过程直到X能被放入空穴为止。

deleteMin

删除根元素,根节点建立一个空穴,将空穴的两个儿子中较小者移入空穴,这样就把空穴乡下推了一层,重复该步骤直到X可以被放入空穴中。
需要考虑堆中存在偶数个元素的时候,将遇到一个节点只有一个儿子的情况

优先队列的应用

选择问题

java标准库中的优先队列

未完待续

开发者首页 wechat
欢迎您扫一扫上面的微信公众号