1.堆排序
a.堆的定义
n个元素序列{k1,k2,...,kn}当且仅当满足以下关系时,称之为堆。
ki<=k2i且ki<=k2i+1 （小根堆) ki>=k2i且ki>=k2i+1 （大根堆)
以下针对最大堆
b.维护堆的性质
Max-Heapify通过让A[i]的值在最大堆中"逐级下降"(A[i]的值小于其左右孩子的值时),从而使得以i为根结点的子树重新遵循最大堆性质.
Max-Heapify(A,i) l = left(i) r = right(i) if l <= A.heap-size and A[l] > A[i] largest = l else largest = i if r <= A.heap-size and A[r] > A[largest] largest = r if largest ≠ i swap(A[i],A[largest]) Max-Heapify(A,largest)
时间复杂度:O(lgn)
c.建堆
子数组A(n/2+1..n)中的元素都是树的叶子结点,每个叶结点都可以看成只包含一个元素的堆.Build-Max-Heap对树中的其他结点都调用一次Max-Heapify.
Build-Max-Heap(A) A.heap-size = A.length for i = A.length/2 downto 1 Max-Heapify(A,i)
时间复杂度:O(n)
d.堆排序
Heap-Sort(A) Build-Max-Heap(A) for i = A.length downto 2 swap(A[1],A[i]) A.heap-size = A.heap-size -1 Max-Heapify(A,1)
时间复杂度:O(n*lgn)
2.优先队列
具体的算法就不谈了,来看下C++中的优先队列如何使用.
std::priority_queue Defined in header <queue> template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue;
默认是最大优先队列.可以提供Compare参数来实现最大优先队列.
Compare = greater<T>
Example:
#include <functional> #include <queue> #include <vector> #include <iostream> template<typename T> void print_queue(T& q) { while(!q.empty()) { std::cout << q.top() << " "; q.pop(); } std::cout << ‘\n‘; } int main() { std::priority_queue<int> q; for(int n : {1,8,5,6,3,4,0,9,3,2}) q.push(n); print_queue(q); std::priority_queue<int, std::vector<int>, std::greater<int> > q2; for(int n : {1,8,5,6,3,4,0,9,3,2}) q2.push(n); print_queue(q2); }
对于自定义类型
如果重载了比较运算符
priority_queue<T> Q//最大优先队列 priority_queue<T,vector<T>,greater<T>> Q//最小优先队列
如果没有重载比较运算符,则需要提供一个Comparator传给Compare参数
//最大优先队列比较器 struct comp { bool operator () (T &a,T &b) const { return a.key < b.key; } }; //最小优先队列比较器 struct comp { bool operator () (T &a,T &b) const { return a.key > b.key; } }; //使用 priority_queue<T,vector<T>,comp> Q
原文：http://www.cnblogs.com/bukekangli/p/4395962.html
