c++堆

c++ reference: http://www.cplusplus.com/reference/algorithm/make_heap/

heap并不属于STL容器组件，它分为 max heap 和min heap，在缺省情况下，max-heap是优先队列（priority queue）的底层实现机制。

而这个实现机制中的max-heap实际上是以一个vector表现的完全二叉树（complete binary tree）。

二叉堆（binary heap）就是i一种完全二叉树。也即是。整棵二叉树除了最底层的叶节点以外，都是填满的，而最低层的叶子结点必须是从左到右不留空隙。

至于max-heap和min-heap，前者的任何一个父亲结点都必须大于等于他的任意子结点，而后者相反。

下面我们利用数组来隐式表达这棵数：

第0号元素保留，从arry[1]开始保存A，这时候我们可以轻易的看到：

位于位置i的某个结点arry[i]，他的左子结点必然在arry[2*i]中，右子结点必然位于arry[2*i+1]，其父亲结点必然位于arry[i/2]处。

这种数组表达的方式我们 称为 隐式表达。

当然由于arry大小是静态的，不能动态添加元素，我们可以使用vector来实现。

heap-算法：

1. push_heap()，新添加一个元素在末尾，然后重新调整堆序。也就是把元素添加在底层vector的end()处。

该算法必须是在一个已经满足堆序的条件下，添加元素。该函数接受两个随机迭代器，分别表示first,end,区间范围。

关键是我们执行一个siftup()函数，上溯函数来重新调整堆序。具体的函数机理很简单，可以参考我的编程珠玑里面堆的实现的文章。

2. pop_heap()，这个算法跟push_heap类似，参数一样。不同的是我们把堆顶元素取出来，放到了数组或者是vector的末尾，用原来末尾元素去替代，

然后end迭代器减1，执行siftdown()下溯函数来重新调整堆序。

注意算法执行完毕后，最大的元素并没有被取走，而是放于底层容器的末尾。如果要取走，则可以使用底部容器（vector）提供的pop_back()函数。

3. sort_heap()，既然每次pop_heap可以获得堆中最大的元素，那么我们持续对整个heap做pop_heap操作，每次将操作的范围向前缩减一个元素。

当整个程序执行完毕后，我们得到一个非降的序列。

同理，sort_heap(RamdomAccessIteraor first,RamdomAccessIteraor end)接受两个随机迭代器作为参数。表示操作的范围。

注意这个排序执行的前提是，在一个堆上执行。执行完之后序列也就失去了堆的性质。

#include iostream 

#include cstdio 

#include cstring 

#include algorithm 

#include vector 

#include deque 

#include map 

#include set 

#include sstream 

using namespace std;

void outHeap(vector int v){

 for(int i=0; i v.size(); ++i)

 cout v[i] " ";

 cout endl;

int main(){

 int myints[] = {10,20,30,5,15};

 vector int v(myints,myints+5);

 cout "建堆:" endl;

 make_heap(v.begin(), v.end());

 outHeap(v);

 cout endl;

 cout "往堆里插入一个元素:" endl;

 v.push_back(100);

 push_heap(v.begin(), v.end());

 outHeap(v);

 cout endl;

 cout "弹出堆顶元素，输出下一个堆顶元素:" endl;

 cout "当前堆顶元素: " v.front() endl;

 pop_heap(v.begin(), v.end());

 v.pop_back();

 cout "下一个堆顶元素: " v.front() endl;

 cout endl;

 cout "排序堆:" endl;

 sort_heap(v.begin(), v.end());//默认从小到大 

 //sort_heap(v.begin(), v.end(), greater int 

 outHeap(v);

 //通过multiset实现最小堆 

 cout endl "通过multiset实现最小堆:" endl;

 multiset int mst(myints,myints+5);

 for(multiset int ::iterator it = mst.begin(); it!=mst.end(); ++it) 

 cout *it " ";

 cout endl;

 return 0;

}

4.一道很经典的题目就是在1亿个数中找到最大的前100个数，这是一道堆应用题，找最大的前100个数，那么我们就创建一个大小为100的最小化堆，每来一个元素就与堆顶元素比较，因为堆顶元素是目前前100大数中的最小数，前来的元素如果比该元素大，那么就把原来的堆顶替换掉并重新调整堆。

5.例题：lintcode 滑动窗口的中位数 : http://www.lintcode.com/zh-cn/problem/sliding-window-median/

//最无脑的解法....

class Solution {

public:

 * @param nums: A list of integers.

 * @return: The median of the element inside the window at each moving

 vector int medianSlidingWindow(vector int nums, int k) {

 vector int 

 vector int res;

 if (k nums.size() || k == 0) return res;

 for(int i=0; i ++i)

 v.push_back(nums[i]);

 sort(v.begin(), v.end());

 res.push_back(v[(k-1)/2]);

 for(int i=k; i nums.size(); ++i){

 v.erase(lower_bound(v.begin(), v.end(), nums[i-k]));

 v.insert(lower_bound(v.begin(), v.end(), nums[i]), nums[i]);

 res.push_back(v[(k-1)/2]);

 return res;

};

//使用multiset进行优化（内部以平衡二叉树），感觉和上面的"最脑的解法差不多"， 只不过是将一个有序的序列分成左右连个连续的序列，左边序列的最后一个就是中位数

class Solution {

public:

 * @param nums: A list of integers.

 * @return: The median of the element inside the window at each moving

 vector int medianSlidingWindow(vector int nums, int k) {

 // write your code here

 vector int res;

 if (k nums.size() || k == 0) return res;

 multiset int left, right;

 //init heaps by first kth elements in nums

 for (int i = 0; i ++i) {

 left.insert(nums[i]);

 while (left.size() (k + 1) / 2) {

 right.insert(*left.rbegin());

 left.erase(left.find(*left.rbegin()));

 res.push_back(*left.rbegin());

 //slide window

 for (int i = k; i nums.size(); ++i) {

 //delete the leftmost element in window from heaps

 if (nums[i-k] res.back()) right.erase(right.find(nums[i-k]));

 else left.erase(left.find(nums[i-k]));

 //insert new element into heaps

 if (!left.empty() nums[i] = *left.rbegin()) left.insert(nums[i]);

 else right.insert(nums[i]);

 //adjust heaps so that the left heap contains (k + 1) / 2 elements

 if (left.size() (k + 1) / 2) {

 left.insert(*right.begin());

 right.erase(right.begin());

 } else if (left.size() (k + 1) / 2) {

 right.insert(*left.rbegin());

 left.erase(left.find(*left.rbegin()));

 res.push_back(*left.rbegin());

 return res;

};