堆

什么是堆(用数组实现的二叉树)

• 通过有序的key存储value的数据结构
• 依据程序分为大顶堆和小顶堆
• 通常用来实现优先级队列priority_queue(topk)

二叉堆

• key存在二叉树的节点中
• key必须是可排序的
• 具备堆属性，例如在最大堆中，父节点的值比每一个子节点的值都要大
• get maximum: O(1) (constant time)
• remove maximum: O(log N) (logarithmic time)
• insert: O(log N)
• increase key: O(log N)

用数组示意二叉树

• 满二叉树 共2^h-1个节点
• 齐全二叉树能够被数组示意(Almost full binary trees) ，2^(h-1) -1 ~ 2^h -1 个节点

• left_child_index(p) = 2 * p + 1
• right_child_index(p) = 2 * p + 2

堆操作(c++用相似数组的容器示意)

• cmp 默认是 <
• make_heap(@b, @e, cmp)：将键序列从新排序为二进制堆
• push_heap(@b, @e, cmp)：插入一个新密钥
• pop_heap(@b, @e, @cmp)：删除最大值
• sort_heap(@b, @e, @cmp)：堆→排序数组
• is_heap(@b, @e, @cmp): 判断是否是heap
• 如果只须要一个优先级队列，应用std::priority_queue