heap概述
heap并不是STL容器组件，更像是一组操作的集合。什么是堆：堆是一颗完全二叉树，且任意节点的值不大于（不小于，大根堆）其儿子节点的值。因为heap的完全二叉树，我们可以利用一个array来存储元素，且我们假定根节点位于array[1]的位置，那么其左儿子将放在array[2]处，右儿子在array[2+1]的位置，更为一般的结论是：
假定堆的根节点放在array[1]，那么任意节点i的左右儿子index分别为2i，2i+1。且任意节点i的父节点是i/2。
因此，要实现一个堆，我们只需要一个array和一组基于array的算法就行了，考虑到堆的可扩展性，我们用vector代替array将是一个容易想到的方案。下面将以大根堆为例（STL默认堆），详细描述堆的算法。
heap算法
对于堆的操作，比起其他STL容器可谓是简单到令人发指，主要有：构建堆，新元素入堆，弹出堆顶元素，给堆排序。下面一个个分析。
make_heap
template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last)
{
__make_heap(first, last, value_type(first), distance_type(first));
}
template <class RandomAccessIterator, class T, class Distance>
void __make_heap(
RandomAccessItreator first,
RandomAccessIterator last,
T*, Distance*)
{
if (last - first < 2) return;
Distance len = last - first;
Distance parent = (len - 2) / 2;
while (true) {
__adjust_heap(first, parent, len, T(*(first +parent)));
if (parent == 0) return;
--parent;
}
}
template <class RandomAccessIterator, class Distance, class T>
void __adjust_heap(
RandomAccessIterator first, Distance holeindex, Distance len, T value)
{
Distance topIndex = holeIndex;
Distance secondChild = 2 * holdIndex + 2;
while (secondChild < len) {
// 默认大根堆，应该用comp
// 左右儿子中较大者上升，并递归执行
if (*(first + secondChild) < *(first + secondChild - 1))
--secondChild;
*(first + holeIndex) = *(first + secondChild);
holeIndex = secondChild;
secondChild = 2 * (secondChild + 1);
}
if (secondChild == len)
{
*(first + holeIndex) = *(first + (secondChild - 1));
holeIndex = secondChild - 1;
}
// *(first + holeIndex) = value;
// 把value插在最后，并调整位置
__push_heap(first, holeIndex, topIndex, value);
}
template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last)
{
__push_heap_aux(first, last, distance_type(first), value_type(first));
}
template <class RandomAccessIterator, class Distance, class T>
inline void __push_heap_aux(RandomAccessIterator first, RandomAccessIterator last, Distance*, T*)
{
__push_heap(first, Distance((last-first)-1),Distance(0),T(*(last-1)));
}
template <class RandomAccessIterator, class Distance, class T>
inline void __push_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex, T value)
{
// holeIndex parent都是相对位置，可以为0
// 假设0号位置也存数据，那么节点i的父亲节点为(i-1)/2
// 假设0号位置存数据，节点i的左儿子为2*i+1，右儿子为2*i+2
// holeIndex即为最后一个元素的位置，也就是新push进来的元素
// topIndex为堆顶元素位置，且从堆顶到末尾（除去新插入的元素）
// 已经构成堆，否则进行push_heap没有意义，即从[first, first + holeIndex - 1]成堆
Distance parent = (holeIndex - 1) / 2;
while (holeIndex > topIndex && *(first + parent) < value) {
*(first + holeIndex) = *(first + parent);
holeIndex = parent;
parent = (holeIndex - 1) / 2;
}
*(first + holeIndex) = value;
}
template <class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last)
{
__pop_heap_aux(first, last, value_type(first));
}
template <class RandomAccessIterator, class T>
inline void __pop_heap_aux(
RandomAccessIterator first,
RandomAccessIterator last, T*)
{
__pop_heap(first, last-1, last-1, T(*(last-1)),distance_type(first));
}
template <class RandomAccessIterator, class T,class Distance>
inline void __pop_heap(RandomAccessIterator first,
RandomAccessIterator last,
RandomAccessIterator result,
T value, Distance*)
{
*result = *first;
__adjust_heap(first, Distance(0),Distance(last-first),value);
}
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first,
RandomAccessIterator last) {
while (last - first > 1)
pop_heap(first, last--);
}
通俗易懂时刻：
- push_heap操作是在原有堆的基础上，在末端先插入一个元素，自然插入之后就不满足堆的性质了，必须调整，这个调整只需要在插入位置及其祖先调整，即不断往父亲方向交换。直到位置合适。
- pop_heap操作也是在原有堆的基础上，因为pop的是堆顶元素，他先保存了整个堆的最后一个元素，把最后一个元素位置腾挪出来，把要pop的这个元素放在那，然后在堆顶处开始调整，即将左右儿子中较大者扶持上来，成为新的顶，并递归操作，直到没有左右儿子，把之前保存的整个堆的最后一个元素放下，此时可能并不满足堆的性质，需要将这个元素再上溯一次，进行调整。
- make_heap从最后一个元素的父亲（节点i）开始，到第一元素节点0，做如下操作：调整以i节点为堆顶的子堆，只需要把自己和左右儿子比较，如果合适就不用换，否则与左右儿子中较大者交换，并递归下去。
- sort_heap一个个pop出元素，自然就排好序了
heap实测
/*
5
4 2
1 3 6 7
注：5的两个儿子分别为4 2，此时并不是堆
*/
vector<int> arr = {5,4,2,1,3,6,7};
make_heap(arr.begin(), arr.end());
/*
原序列，并将其调整为大根堆：
5
4 2
1 3 6 7
1次调整，从最后一个元素（7）的父亲（2）开始调整，将元素2和其左右儿子较大的交换：
5 5
4 2 4 (2)->7
1 3 6 7 1 3 6 (7)->2
2次调整，从元素4调整，将元素4和左右儿子较大的交换，因比左右儿子大，合适，不用交换：
5 5
4 7 4 7
1 3 6 2 1 3 6 2
3次调整，从元素5调整，将元素5和左右儿子较大的(7)交换
交换后，以元素5为顶的堆仍然需要调整，因为元素5比其左儿子6小
5 (5)->7
4 7 4 (7)->5
1 3 6 2 1 3 6 2
7 7
4 5 4 (5)->6
1 3 6 2 1 3 (6)->5 2
至此满足一个大根堆的性质，建堆完毕
*/
arr.push_back(8);
push_heap(arr.begin(), arr.end());
/*
操作arr.push_back(8)后，并不满足堆性质了，需要在插入位置进行上溯
7
4 6
1 3 5 2
8
step1:
7
4 6
(1)->8 3 5 2
(8)->1
step2:
7
(4)->8 6
(8)->4 3 5 2
1
step3:
(7)->8
(8)->7 6
4 3 5 2
1
调整完毕
*/
pop_heap(arr.begin(), arr.end());
/*
当前堆：
8
7 6
4 3 5 2
1
step1,保存最后一个元素(1)，把堆顶元素(8)放到最后(元素1)的位置
x
7 6
4 3 5 2
8
此时保存value=1，留作备用，此时位置x是空的，需要找继承人，从左右儿子中较大中找
step2
x (x)->7
7 6 (7)->x 6
4 3 5 2 4 3 5 2
8 8
step3
7 7
x 6 (x)->4 6
4 3 5 2 (4)->x 3 5 2
8 8
此时已经结束，因为8这个位置已经是不存在的了，把value=1放在x位置，
新堆如下起始结束位置为元素7到元素2，元素8已经不属于堆了，但是仍然在数组中
7
4 6
1 3 5 2
8
*/
网友评论