STL中heap相关函数的用法

发表于 |

函数说明

参数都是一样的：

make_heap(first ,last)
make_heap(first ,last, cmpObject)

将[first, last)范围进行堆排序，默认使用less<int>, 即最大元素放在第一个。

pop_heap(first ,last)
pop_heap(first ,last, cmpObject)

将front（即第一个最大元素）移动到end的前部，同时将剩下的元素重新构造成(堆排序)一个新的heap。

push_heap(first ,last)
push_heap(first ,last, cmpObject)

对刚插入的（尾部）元素做堆排序。

sort_heap(first ,last)
sort_heap(first ,last, cmpObject)

将一个堆做排序,最终成为一个有序的系列，可以看到sort_heap时，必须先是一个堆（两个特性：1、最大元素在第一个 2、添加或者删除元素以对数时间），因此必须先做一次make_heap.

Sample 1

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

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
33
34
35
36
37
class Solution {
    vector<int> min, max; // as heap
public:
    void Insert(int num) {
        if (((min.size() + max.size()) & 0x1) == 0) {
            if (max.size() > 0 && num < max[0]) {
                max.push_back(num);
                push_heap(max.begin(), max.end(), less<int>());
                num = max[0];
                pop_heap(max.begin(), max.end(), less<int>());
                max.pop_back();
            }
            min.push_back(num);
            push_heap(min.begin(), min.end(), greater<int>());
        } else {
            if (min.size() > 0 && num > min[0]) {
                min.push_back(num);
                push_heap(min.begin(), min.end(), greater<int>());
                num = min[0];
                pop_heap(min.begin(), min.end(), greater<int>());
                min.pop_back();
            }
            max.push_back(num);
            push_heap(max.begin(), max.end(), less<int>());
        }
    }

    double GetMedian() {
        if (min.size() + max.size() == 0) return 0; // Error
        
    	if (((min.size() + max.size()) & 0x1) == 0) {
            return ((double)min[0] + (double)max[0]) * 0.5;
        } else {
            return (double)min[0];
        }
    }
};

Sample 2

来自：http://www.cnblogs.com/coderyoyo/archive/2011/01/21/stl_heap.html

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main () {
  int myints[] = {10,20,30,5,15};
  vector<int> v(myints,myints+5);
  vector<int>::iterator it;
 
  make_heap (v.begin(),v.end());
  cout << "initial max heap   : " << v.front() << endl;
 
  pop_heap (v.begin(),v.end()); v.pop_back();
  cout << "max heap after pop : " << v.front() << endl;
 
  v.push_back(99); push_heap (v.begin(),v.end());
  cout << "max heap after push: " << v.front() << endl;
 
  sort_heap (v.begin(),v.end());
 
  cout << "final sorted range :";
  for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
 
  cout << endl;
 
  return 0;
}

Ref.

  1. 堆算法(make_heap,push_heap,pop_heap, sort_heap)
  2. 剑指Offer
  3. Cplusplus.com