堆分为两种：最⼤堆和最⼩堆，两者之间的差别在于节点的排序⽅式。
- 最⼤堆：⽗节点的值⽐每⼀个字节点的值都⼤。
- 最⼩堆：⽗节点的值⽐每⼀个字节点的值都⼩。
- 堆常常被当作优先队列来⽤，因为可以快速的访问到“最重要”堆元素.
堆和普通树的区别
堆不能取代⼆叉搜索树，它们之间有相似之处也有⼀些不同。
- 节点的顺序：在⼆叉搜索树中，左⼦节点必须⽐⽗节点⼩，右⼦节点必须⽐⽗节点⼤。⽽堆并⾮如此。
- 内存占⽤：普通树占⽤的内存空间⽐它们存储的数据要多。你必须为节点对象以及左/右节点指针分配• 额外多内存。⽽堆仅仅使⽤⼀个数组进⾏存储，且不⽤指针。
- 平衡：⼆叉搜索树必须是“平衡”堆情况下，其⼤部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插⼊/删除数据，或者使⽤AVL树或者红⿊树，但是堆中实际上不需要整棵树都是有序的。我们只 需要满⾜堆属性即可，所以在堆中平衡不是问题。因为堆中的数据的组织⽅式可以保证O(log n)的性 能。。
- 搜索：在⼆叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第⼀优先级因为使⽤堆的⽬的是将最⼤（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。
⽤数组存储堆
对于任意⼀个堆，如下图，⾃上⽽下，从左到右把堆中的数据存放到数组⾥。
现在的问题是：⽤数组存储堆，那么就⽤不了指针，那怎么找到某⼀个节点的⽗节点和⼦节点呢？
对任意⼀个节点，i是他的索引，那么：
- 其父节点：\(floor((i-1)/2)\)
- 其左右子节点：\(2*i+1, 2*i + 2\)
如何快速查找到最后一个非叶子节点：
- \((n-1)/2\)
代码
建堆
void make_heap(int* array, int size)
{
for(int i=(size-1)/2; i>=0; --i)
{
// 从索引（size-1）/2 开始，调整堆
adjust_heap(array, i, size);
}
}
void adjust_heap(int* array, int node, int size)
{
int left = 2 * node + 1;
int right = 2 * node + 2;
int max = node;
if(left < size && array[left] > array[max]){
max = left;
}
if(right < size && array[right] > array[max])
{
max = right;
}
if(node != max)
{
swap(array[max], array[node]);
adjust_heap(array, max, size);
}
}用堆排序数组
已知有一个最大堆，对数组进行非递减排序：
将堆的顶部，与最后一个元素交换。此时除了最后一个元素外，剩下元素所组成的树已经不是堆了。（因为此时顶部的元素可能比较小）。所以，要将剩下的元素通过 adjust函数调整成堆。
for(int i=size-1; i>=0; i--)
{
swap(array[0], array[i]);
adjust_heap(array, 0, i);
}时间复杂度
- 堆排序时间复杂度：\(O(n log n)\)
- 建堆的时间复杂度：\(O(n log n)\)
- 调整堆的复杂度：\(O(log(n))\)