堆及其C++实现

堆的定义

堆是一棵节点含有比较器的完全二叉树。

堆的存储

在标准库中可以使用std::priority_queue（默认最大值堆）实现，也可以使用std::vector结合std::make_heap（默认最大值堆）实现。

本质上都是使用数组实现的，并以数组的下标建立父子节点关系，无需额外维护指针，占用空间小。

i的父亲节点下标：floor((i-1)/2)。

i的左子节点下标：2i+1

i的右子节点下标：2i+2，可以看出左右子节点一定相邻，代入数字我们可以得到134，256等等具体关系。

堆算法的核心

下移操作是堆算法的核心，对某个节点的下移操作相当于比较当前节点与其左右子节点的相对大小。

最大值堆满足3个特性

1）f[floor((i-1)/2)]>=f[i]

部分有序，嗯，只是部分有序。

2）插入（将新元素插入堆的末尾，上移操作）

将新元素插入堆的末尾，并且与父节点进行比较，如果新节点的值大于父节点，则与之交换，即上移，直至操作 无法进行。

3）删除（弹出堆顶元素，下移操作）

堆尾代替堆顶的位置，然后执行下移操作。

建最大值堆

从n/2（第n/2个节点）一直到根结点（第1个节点），依次进行下移操作。

比如对于{2，3，4，1，5，9}建堆，结果就是{9，5，4，1，3，2}。

使用std::make_heap建堆（默认最大值堆）时，用的应该就是这种方法。

注：同样的元素以不同的顺序一个一个插入所建的堆是不一样的，而且使用的是上移操作，因为这个过程本质上就是插入，而非建堆，所谓的建堆应该指的是没有新元素加入，是已有元素的调整。

---

C++实现

1）优先队列

#include <queue>

std::priority_queue<...>

2）数组

#include <algorithm>

#include <functional>

std::is_heap(v.begin(), v.end());

std::make_heap(v.begin(), v.end());

最大值堆：std::make_heap(v1.begin(), v1.end());

最小值堆：std::make_heap(v1.begin(), v1.end(), std::greater<>{});

std::push_heap(v.begin(), v.end());  

需要先执行v.push_back()，再执行std::push_heap()。

std::pop_heap(v.begin(), v.end());

这一步操作并没有真正地删除元素，只是将堆顶元素移至最后，若要真的删除，还需执行v.pop_back()。