优先队列
满足操作:
- 插入一个数值
- 取出最小的数值(获得数值,并且删除)
实现:堆(二叉搜索树)
堆
性质:二叉树,儿子的值一定不小于父亲的值。
初始堆
插入数值举例,向初始堆中插入数值3时,首先在堆的末尾插入该数值,然后不断向上提升直到没有大小颠倒为止。
取出最小值举例,从堆中删除最小值时,首先把堆的最后一个节点的数值复制到根节点上,并且删除最后一个节点。然后不断向下交换直到没有大小颠倒为止。在向下交换的过程中,如果有2个儿子,选择数值较小的儿子进行交换。
堆操作的时间复杂度
堆的两种操作所花的时间都和树的深度成正比。
如果一共有n个元素,那么每个操作可以在O(logn)
的时间内完成。