1
 2
 3
 4
 5
 6
 7
 8
 9
10

template<typename T>
void push_heap(std::vector<T> &vec, T value)
{
	vec.push_back(value);
	int i = vec.size()-1;
	while (i > 1 && vec[i] > vec[i / 2]) {
		std::swap(vec[i], vec[i / 2]);
		i = i / 2;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

template<typename T>
T pop_heap(std::vector<T> &vec)
{
	int i = 1;
	//将最后元素与第一个元素(根元素)交换, 然后删除最后一个元素
	std::swap(vec[1], vec[vec.size() - 1]);
	T v = vec[vec.size() - 1];
	vec.pop_back();

	//将现在的第一个元素/根元素下沉到一个合适的位置
	while (2 * i < vec.size()) {
		int j = 2 * i;	//左子节点
		if (j < vec.size() - 1 && vec[j] < vec[j + 1]) j++;
		if (vec[j] < vec[i]) break;
		std::swap(vec[i], vec[j]);
		i = j;
	}
	return v;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

template<typename T>
void sort_heap(std::vector<T> &vec)
{
	std::vector<T> temvec;
	int size = vec.size()-1;
	while (size != 0) {
		temvec.push_back(pop_heap(vec));
		size--;
	}
	for (T value : temvec) {
		vec.push_back(value);
	}
}

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#include <iostream>
#include <vector>
 
#ifdef __STL_USE_EXCEPTIONS
#define __STL_TRY   try
#define __STL_UNWIND(action)   catch(...) { action; throw; }
#else
#define __STL_TRY
#define __STL_UNWIND(action)
#endif
 
 
template <class T,class Sequence = std::vector<T>,
          class Compare = std::less<typename Sequence::value_type>>
class priority_queue{
public:
    typedef typename Sequence::valuetype value_type;
    typedef typename Sequence::size_type size_type;
    typedef typename Sequence::reference reference;
    typedef typename Sequence::const_reference const_reference;
protected:
    Sequence c; //底层容器
    Compare comp; //元素大小的比较标准
public:
    priority_queue() : c (){}
    explicit priority_queue(const Compare& x) : c() ,comp(x){}
    //以下使用的make_heap()、push_heap()、pop_heap()都是泛型算法
    //注意 任意一个构造函数都立刻在底层容器内产生一个implicit representation heap
    //指代比较器
    template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last,const Compare& x):
    c(first,last),comp(x){
        std::make_heap(c.begin(),c.end(),comp);
    }
    //没有指代比较器
    template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last):
            c(first,last){
        std::make_heap(c.begin(),c.end(),comp);
    }
    bool empty()const{
        return c.empty();
    }
    size_type size() const{
        return c.size();
    }
    const_reference top()const{
        return c.front();
    }
    void push(const value_type& x){
        __STL_TRY{
            //push_heap 是泛型算法，先利用底层的push_back()将新的元素推入末端，再重新排列heap
            c.push_back(x);
            //push_heap 是泛型算法
            std::push_heap(c.begin(),c.end(),comp);
        }
        __STL_UNWIND(c.clear());
    }
    void pop(){
        __STL_TRY{
            //pop_heap是泛型算法，从heap中取出一个元素，并不是整整将这个元素弹出，而是重排heap
            //需要使用底层vector的pop_back()取得被弹出的元素
            std::pop_heap(c.begin(),c.end(),comp);
            c.pop_back();
        }
        __STL_UNWIND(c.clear());
    }
 
};

1

priority_queue<string> pq;//也可以是 int,char等

1

priority_queue<int,vector<int>,less<int>> pq;