|
定义
优先队列是利用堆来实现的，堆可以看做是一棵完全二叉树的顺序存储结构。在这棵二叉树中，如果每一个节点的值都大于等于左右孩子的值，则称之为“最大堆”。如果每一个节点的值都小于等于左右孩子的值，则称之为“最小堆”。
应用
在算法设计中，经常用到从序列中找一个最小值(最大值)的操作，例如最短路径，哈夫曼编码等都需要找到一个最小值，如果从序列中顺序查找最值需要
O
(
n
)
O(n)
O(n) 的时间。而从优先队列中查找最值，则需要
O
(
l
o
g
n
)
O(logn)
O(logn)的时间。 优先队列中堆的创建需要
O
(
n
)
O(n)
O(n)的时间（下面讲解原因），而取最值只需要
O
(
l
o
g
n
)
O(logn)
O(logn)的时间。也就是二叉树的高度。
python创建最大堆
# coding=utf-8
class Heap(object):
def __init__(self, nums):
"""
创建最大堆
:param nums:
"""
self.nums = nums
self.length = len(nums)
def _sink(self, k):
"""
节点下沉
:param k:
:return:
"""
while 2 * k |