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>v;vector<int> res;if (k > nums.size() || k == 0) return res;for(int i=0; i<k; ++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 herevector<int> res;if (k > nums.size() || k == 0) return res;multiset<int> left, right;//init heaps by first kth elements in numsfor (int i = 0; i < k; ++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 windowfor (int i = k; i < nums.size(); ++i) {//delete the leftmost element in window from heapsif (nums[i-k] > res.back()) right.erase(right.find(nums[i-k]));else left.erase(left.find(nums[i-k]));//insert new element into heapsif (!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 elementsif (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;}
};

?