堆 Heap

Heap：可以迅速找到一堆数中的最大或者最小值的数据结构

将根节点最大的堆叫做大顶堆或大根堆，根节点最小的堆叫做小顶堆或小根堆。
常见的堆有二叉堆、斐波那契堆等。

假设是大顶堆，则常见操作（API）：

• find-max: O(1)
• delete-max: O(logn)
• insert(create): O(logn) 或 O(1)

不同实现的比较：https://en.wikipedia.org/wiki/Heap_(data_structure))

二叉堆性质

通过完全二叉树来实现（注意：不是二叉搜索树）

• 完全二叉树：就是它的根和每一级结点都是满的

二叉堆（大顶）它满足下列性质：

• 【性质一】是一颗完全树
• 【性质二】树中任意节点的值总是 >= 其子节点的值

、

二叉堆实现细节

1. 二叉堆一般都通过“数组”来实现

[110, 100, 90, 40, 80, 20, 60, 10, 30, 50, 70]

1. 假设“第一个元素”在数组中的索引为 0 的话，则父节点和子节点的位置关系如下：

（1）索引为 i 的左孩子的索引是 （2 i + 1）
（2）索引为 i 的右孩子的索引是（2 i + 2）
（3）索引为 i 的父结点的索引是 floor((i - 1) / 2)
（4）跟结点 a[0]

Insert 插入操作 - O(logn)

1. 新元素一律先插入到堆的尾部
2. 依次向上调整整个堆的结构（一直到根即可）

HeapifyUp