STL：heap_牛客博客

写在前面

STL:heap

主要内容

heap是什么

heap并不是STL的容器，是以算法的方式出现的。扮演priority_queue的幕后英雄。
priority_queue采用的底层机制就是heap。这里需要注意heap并不是一种二叉搜索树，更不是平衡的二叉搜索树比如AVL树和红黑树。

heap其实是一种完全二叉树。
完全二叉树：除了最低风层的叶子结点之外，是填满的。最底层的叶子结点由右往左不得有空隙。
特性：可以利用数组下标定位父结点和子结点。

如果将数组的0号位置保留，从1号位置填充结点那么某个结点在i位置时，其左孩子在2i，右孩子在2i+1，其父节点必然在i/2的位置。这种使用数组表示树的方法就是隐式表示法。

heap的组成

一个数组，一组heap算法用于实现操作，插入元素，删除元素，取极值，将某一个区间的数据排列成一个heap。
原生数组无法动态改变大小，但是vector可以，所以使用vector。

heap的分类

根据元素的排列方式，heap分为最大堆和最小堆。
最大堆：每个结点的值都大于等于其子节点的值。
最小堆：每个结点的值都小于等于其子节点的值。
这样最大堆的最大值在根，也就在底层数组的头部，最小堆的最小值也在根，也在数组的头部。
这样只要能够维持这个堆我们就可以很方便的o(1)的时间复杂度得到最大堆的最大值，最小堆的最小值。

heap算法

定义于头文件 < algorithm>
push_heap:

有两种一种2个参数的默认以最大堆方式进行，另一种三个参数的重载版本可以指定比较函数。
插入位于位置 last-1 的元素到范围 [first, last-1) 所定义的最大堆中。
函数的第一版本用 operator< 比较元素，第二版本用给定的比较函数 comp 。

template< class RandomIt >
void push_heap( RandomIt first, RandomIt last );
template< class RandomIt, class Compare >
void push_heap( RandomIt first, RandomIt last, Compare comp );

分析：
将元素插入堆当中分为两步，首先先将元素push_back到底层数组的最后。
将底层容器的首尾迭代器传递给push_heap算法（可以指定比较方式）
less< T>是最大堆，greator< T>是最小堆

为什么less< T> 使用小于号比较结果还是最大堆？

因为在插入的结点的时候会不断与其父节点进行比较如果父节点的值小于插入结点的值插入结点就要和父节点对调位置，也就是插入结点要向上上溯。这里采用的比较是父节点的值<当前结点的值就上溯。那么上溯到根结点的值必然是最大值也就是构成了最大堆。同理如果采用greator< T> 比较，就是父节点的值 > 当前结点的值就上溯，那么上溯到根结点的值必然是最小值，就构成了最小堆。

pop_heap算法

同样也是两个版本：

template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last );
template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp );

交换在位置 first 的值和在位置 last-1 的值，并令子范围 [first, last-1) 变为最大堆。
这拥有从范围 [first, last) 所定义的堆移除首个（最大）元素的效应。
函数的首个版本使用 operator< 比较元素，第二版本使用给定的比较函数 comp 。

整个操作分为几部分：
首先移除堆顶元素：就是将堆顶元素和堆尾元素互换位置。也就是将底层数组的首尾元素互换。
其次对底层数组的[first,last-1)的位置进行调整维持一个长度减一的堆。
可从底层数组的尾部取出被pop出的最大元素。
因为每次都是和尾部结点互换所以维持了完全二叉树的性质。

如何维持堆？
对于最大堆：当你pop出堆顶元素的时候，堆顶元形成一个空洞，我们无非就是想要找到这个空洞的合适位置将割舍的尾部结点填充进去即可。所以可以分为两步：第一步将空洞结点和其最大的子节点互换位置直到其到达叶子结点，将割舍的结点的值填充进去再对该结点进行一次上溯即可。

sort_heap:

每次pop_hea可以将最大堆当中的最大元素放置在底层数组的末尾，如果持续对整个堆进行pop_heap并且每次操作范围向前减一，最后将得到一个递增的序列。实现非常简单。

template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
  while (last - first > 1) pop_heap(first, last--);
}

make_heap:

将一段现有的数据转化为一个heap。
在范围 [first, last) 中构造最大堆。函数第一版本用 operator< 比较元素，第二版本用给定的比较函数 comp 。

template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );
template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last,Compare comp );