堆

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

• 通过有序的 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