1. STL笔记之heap
1.1. 简介
heap（堆）是一种比较复杂的数据结构。不过 STL 已经封装了 heap 的一些操作，比如：创建堆、判断堆、插入一个元素、删除一个元素、以及堆排序。在 STL 中，heap 是以算法的形式提供的，包括下面几个函数：
make_heap()：根据指定的迭代器区间以及一个可选的比较函数（通常为greater<T>()或者less<T>()，其中 T 为一种数据类型），来创建一个 heap，时间复杂度为 O(n)；push_heap()：把指定区间的最后一个元素插入到 heap 中，时间复杂度为 O(logn)；pop_heap()：弹出 heap 顶元素，将其放置于区间末尾，时间复杂度 O(logn)；sort_heap()：堆排序算法，将指定区间的元素进行堆排序，时间复杂度为 O(nlogn)。
C++11 加入了两个新成员：
is_heap()：判断给定区间是否是一个 heap，时间复杂度为 O(n)；is_heap_until()：找出区间中第一个不满足 heap 条件的元素，返回指向该元素的指针。时间复杂度为 O(n)。
因为 heap 都是以算法的形式提供，所以使用这几个函数需要包含如下头文件：1
1.2. 相关算法的使用
使用数组来存储一个堆，也就是堆化数组：1
2
3int arr[] = {2, 14, 4, 16, 6, 5, 3};
vector<int> vec(arr, arr + sizeof(arr)/sizeof(int));
// vector<int> vec{2, 14, 4, 16, 6, 5, 3};
注：下述函数的使用都是代码片段，且使用的比较函数都是 greater<T>()，即小根堆，默认的是 less<T>()，即大根堆。完整代码在本文最后。
1. is_heap()：判断堆
原型：1
2
3
4
5
6
7// 1
template< typename RandomIt >
bool is_heap( RandomIt first, RandomIt last );
// 2
template< typename RandomIt, typename Compare >
bool is_heap( RandomIt first, RandomIt last, Compare comp );
用法示例：1
cout << is_heap(vec.begin(), vec.end()) << endl;
2. is_heap_until()：找出区间中第一个不满足 heap 条件的元素，返回指向该元素的指针。
原型：1
2
3
4
5
6
7// (1) (since C++11)
template< class RandomIt >
RandomIt is_heap_until( RandomIt first, RandomIt last );
// (2) (since C++11)
template< class RandomIt, class Compare >
RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp );
用法示例：1
2vector<int>::iterator iter = is_heap_until(vec.begin(), vec.end(), greater<int>());
cout << "is heap until: " << *iter << endl;
3. make_heap()：构造堆
STL 中的通过 make_heap() 创建的堆，默认是大根堆（max heap）。要改变堆的建立准则，可以自己制定一个比较函数，比如如下第二个版本的第三个参数。第三个参数可填：less<int>() 构造大根堆，greater<int>() 构造小根堆。（注意：要使用其中一个比较函数，在该堆上使用的其他算法也要使用该比较函数）
原型：1
2
3
4
5
6
7// 1
template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );
// 2
template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last, Compare comp );
用法示例：1
make_heap(vec.begin(), vec.end(), greater<int>());
4. push_heap()：插入元素
如果要在堆中插入一个元素，首先要往容器 vector 尾部插入一个元素，然后把新的迭代区间传给 push_heap()，这样新的元素也被插入到堆中。时间复杂度为 O(logn)。
原型：1
2
3
4
5
6
7// 1
template< class RandomIt >
void push_heap( RandomIt first, RandomIt last );
// 2
template< class RandomIt, class Compare >
void push_heap( RandomIt first, RandomIt last, Compare comp );
用法示例：1
2vec.push_back(20);
push_heap(vec.begin(), vec.end(), greater<int>());
5. pop_heap()：弹出元素
弹出的元素默认是根节点的元素。这个算法的作用是交换根结点元素与堆中的最后一个元素，然后把除了尾部元素的剩余区间重新调整成堆。注意，pop_heap() 函数并没有真正的删除元素，最后要使用容器的 pop_back() 来删除元素。
原型：1
2
3
4
5
6
7
8
9
10// 1
template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last );
// 2
template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp );
// Swaps the value in the position first and the value in the position last-1 and makes the subrange [first, last-1) into a max heap.
// This has the effect of removing the first (largest) element from the heap defined by the range [first, last).
用法示例：1
2pop_heap(vec.begin(), vec.end(), greater<int>());
vec.pop_back();
6. sort_heap()：堆排序
该算法实现经典的堆排序算法，通过每次弹出堆顶元素直到堆为空，依次被弹出的元素就组成了有序的序列。STL 中的 priority_queue 既是用 heap 的这个特性来实现的。
注意：使用 sort_heap() 时要确保区间已经是一个堆了，处理过后的区间因为有序，就不再是一个 heap 了。
原型：1
2
3
4
5
6
7// 1
template< class RandomIt >
void sort_heap( RandomIt first, RandomIt last );
// 2
template< class RandomIt, class Compare >
void sort_heap( RandomIt first, RandomIt last, Compare comp );
用法示例：1
sort_heap(vec.begin(), vec.end(), greater<int>());
7. 完整代码示例：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using namespace std;
template<typename T>
ostream& operator<<(ostream& out, vector<T>& vec){
for (int i = 0; i < vec.size(); ++i){
out << vec[i] << ' ';
}
return out;
}
int main(int argc, char **argv)
{
// int arr[] = {2, 14, 4, 16, 6, 5, 3};
// vector<int> vec(arr, arr + sizeof(arr)/sizeof(int));
vector<int> vec{2, 14, 4, 16, 6, 5, 3};
cout << "is heap: " << is_heap(vec.begin(), vec.end()) << endl;
make_heap(vec.begin(), vec.end(), greater<int>());
cout << "make heap: " << vec << endl;
vec.push_back(20);
push_heap(vec.begin(), vec.end(), greater<int>());
cout << "push heap: " << vec << endl;
pop_heap(vec.begin(), vec.end(), greater<int>());
vec.pop_back();
cout << "pop heap: " << vec << endl;
sort_heap(vec.begin(), vec.end(), greater<int>());
cout << "sort heap: " << vec << endl;
vector<int>::iterator iter = is_heap_until(vec.begin(), vec.end(), greater<int>());
cout << "is heap until: " << *iter << endl;
return 0;
}
代码输出为（注意，g++ 编译时需要添加 -std=c++11）：1
2
3
4
5
6is heap: 0
make heap: 2 6 3 16 14 5 4
push heap: 2 6 3 16 14 5 4 20
pop heap: 3 6 4 16 14 5 20
sort heap: 20 16 14 6 5 4 3
is heap until: 16