heap stl
今天重新写了求多个list的代码，感觉代码还是naive。先分析下make_heap, push_heap pop_heap的问题吧。
堆得典型应用是求最值时时间复杂度的优化，另外还有优先队列。
在群里问，大家都没有深入分析里面的实质，这样的态度其实是不好的。有的说，面试还不是重新写一遍heap，但是那是专门考heap的时候，
如果这个是你的代码的一部分，当然是用stl了，你还重新写一个么。
make_heap()是调整整个为堆，从n/2-1->0 逐个FilterDown()，默认是lower，对应的是大顶堆，先暂且记住吧。
pop_heap()这样的：如果是vector的话，swap(p[0],p[size-1]), 然后将size-1个元素调整为堆，所以后面一般还加一个pop_heap(), 具体的调整就是FilterDown(0)，
pop_heap(v.begin(),v.end(),greater
操作完后，v.back()就不属于堆了。
push_heap()这样的：如果还是vector，将v[size-1]向上调整为堆，Filterup(size-1), 也是O(logn)的复杂度。所以通常先push_back。
因此这个代码就变成这样(某微博童鞋的代码，用了其他部分沈略，用了很多C++11的语法)
vector<int> intersect(vector<Node*>& v){
vector<int> ret;
int maxv=(*max_element(v.begin(),v.end(),cmp))->x;
make_heap(v.begin(),v.end(),cmp2);
while(true){
if(v.front()->x==maxv)
ret.push_back(maxv);
if(v.front()->next==nullptr)
break;
v.front()=v.front()->next;
maxv=max(maxv,v.front()->x);
pop_heap(v.begin(),v.end(),cmp2);
push_heap(v.begin(),v.end(),cmp2);
}
return ret;
}
期间显示修改了堆顶为next指针，然后pop_heap 将swap(v[0],v[size-1]), 然后Filterdown(0),这是size已经-1了。
后面push_heap又将之前换到最后的加进来，通过Filterup(size-1), 之前size++了。
有的童鞋可能问，为啥不直接Filterdown(0)呢，因为堆顶换了元素后，直接调整不能保证堆的性质，必须将之前堆的尾放到堆顶Filterdown来调整，具体参照算导。
另外自己写个linklist确实naive，这时尾插法createlinklist用STL list来push_back是非常方便的，第一次和后面的push已经在里面区分好了。
另外今天还回想起遇到的greater
看了这么多，觉得自己有必要写一个heap，于是下午利用闲情逸致写了一个heap，其中heapsort是假象大顶堆，因此有问题，其他部分都是当初小顶堆来实现的。
//0-based
//min-heap
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
int n,minx;//heap size
int a[100000];
int left(int i){
if(2*i+1<n)
return 2*i+1;
else
return -1;
}
int right(int i){
if(2*i+2<n)
return 2*i+2;
else
return -1;
}
void FilterDown(int i);
void FilterUp(int i);
void heap_sort()//assume max heap
{
int times=n;
for(int i=0;i<times-1;i++)//n-1 max in the right place will finish
{
swap(a[0],a[n-1]);
n--;
FilterDown(0);
}
}
void push_heap(int x)
{
n++;
a[n-1]=x;
FilterUp(n-1);
}
void pop_heap()
{
swap(a[0],a[n-1]);
n--;
FilterDown(0);
}
void make_heap()
{
for(int i=(n-1-1)/2;i>=0;i--)
FilterDown(i);
}
void FilterUp(int i)
{
while(i>0)
{
if(a[i]>=a[(i-1)/2])
break;
else
{
swap(a[i],a[(i-1)/2]);
i=(i-1)/2;
}
}
}
void FilterDown(int i)
{
while(i<n)
{
if(left(i)!=-1 && right(i)!=-1)
{
minx=min(a[left(i)],a[right(i)]);
if(a[i]<=minx)
{
break;
}
else
{
if(a[left(i)]==minx)
{
swap(a[left(i)],a[i]);
i=left(i);
}
else
{
swap(a[right(i)],a[i]);
i=right(i);
}
}
}
else if(left(i)!=-1)
{
if(a[i]<=a[left(i)])
break;
else
{
swap(a[i],a[left(i)]);
break;
}
}
else
break;
}
}
void show()
{
for(int i=0;i<n;i++)
printf("%d ",a[i]);
puts("");
}
int main()
{
freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
make_heap();
show();
pop_heap();
show();
push_heap(100);
show();
return 0;
}