数据结构 | 优先队列和堆

优先队列

满足操作:

  • 插入一个数值
  • 取出最小的数值(获得数值,并且删除)

实现:堆(二叉搜索树)

性质:二叉树,儿子的值一定不小于父亲的值。

初始堆
数据结构 | 优先队列和堆

插入数值举例,向初始堆中插入数值3时,首先在堆的末尾插入该数值,然后不断向上提升直到没有大小颠倒为止。
数据结构 | 优先队列和堆
取出最小值举例,从堆中删除最小值时,首先把堆的最后一个节点的数值复制到根节点上,并且删除最后一个节点。然后不断向下交换直到没有大小颠倒为止。在向下交换的过程中,如果有2个儿子,选择数值较小的儿子进行交换。
数据结构 | 优先队列和堆

堆操作的时间复杂度

堆的两种操作所花的时间都和树的深度成正比。
如果一共有n个元素,那么每个操作可以在O(logn)的时间内完成。