什么是堆（heap）
堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。
这里的堆不是jvm内存模型中的堆，大家不要弄混了。
定义
- 堆是是一颗完全二叉树。[1]
- 堆中某个结点的值总是不大于或不小于其父结点的值；ki >= k2i +1 且 ki >= k2i + 2。
大根堆
规则:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
大根堆
小根堆
规则:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
小根堆
堆的构建
堆的构建一般分为两步：
- 第一步是堆化，从堆中的满二叉树尾部开始，构建成一个堆。
- 把最大或者最小元素移动到数组尾部，然后重新把堆顶元素进行构建
常见的堆
有二叉堆、斐波那契堆等；
-
这叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树 ↩
