堆

什么是堆（heap）

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

这里的堆不是jvm内存模型中的堆，大家不要弄混了。

定义

1. 堆是是一颗完全二叉树。^[1]
2. 堆中某个结点的值总是不大于或不小于其父结点的值；k_i >= k_2i +1 且 k_i >= k_2i + 2。

大根堆

规则:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

大根堆

小根堆

规则:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

小根堆

堆的构建

堆的构建一般分为两步：

1. 第一步是堆化，从堆中的满二叉树尾部开始，构建成一个堆。
2. 把最大或者最小元素移动到数组尾部，然后重新把堆顶元素进行构建

常见的堆

有二叉堆、斐波那契堆等；

1. 这叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树 ↩