heap的实现

binary heap是一种complete binary tree(完全二叉树)也就是说,整棵树binary tree除了最底层的叶节点之外,是填满的.而最底层的叶节点(s)
由左至右又不得有空隙 如图是一个complete binary tree.

使用了一个小技巧 就是将array数组的#0元素保留(或设为最大值或这无限小值),那么当complete bianry tree中的某个节点位于array的i处时,其左子节点
比位于array的2i处,其右子节点比位于array的2i+1处,父节点比位于i/2处.
根据元素的排列方式heap可分为max-heap和min-heap两种.前者每个节点的键值都大于或等于其子节点的键值.后者每个节点的键值都小于或等于其子节点的键值.因此
max-heap的最大值在根节点,并总是位于底层的array或者vector的起头出处

//push_heap的算法
/**
下面是push_heap算法的实现细节,该元素接受两个迭代器,用来表现一个heap底部容器(vector)的头尾,并且新元素已经插入到底部容器的最尾端.
*/
这是图示

template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first,RandomAccessIterator last){
	//注意,此函数被调用时,新元素已经置于底部容器的最尾端
	__push_heap_aux(first,last,distance_type(first),value_type(first));

}
template <class RandomAccessIterator ,class Distance,class T>
inline void __push_heap(RandomAccessIterator first,Distance holeIndex,Distance *,T *){
	__push_heap(first,Distance((last-first)-1),Distance(0),T(*(last-1)));
	//以上系根据implicit representation heap的结构特性,新值必须位于底部
	//容器的最尾端,此即第一个洞号:(last-first)-1	
}
	//一下这组push_back()不允许指定"大小比较标准"
template <class RandomAccessIterator first, class Distance,class T>
void __push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value){
	Distance parent=(holeIndex-1)/2;//找出父节点
	while (holeIndex>topIndex&&*(first+parent)<value){
	//尚未达到顶端,且父节点小于新值(于是不符合heap的次序特性)
	//由于以上使用operator<,可知STL heap是一种max-heap(大者为父)
	*(first+holeIndex)=*(first+parent);//令洞值为父值
	holeIndex=parent;//调整洞号,向上提升至父节点
	parent=(holeIndex-1)/2;//新洞的父节点
}//持续至顶端 或满足heap的次序特性为止
*(first+holeIndex)=value;//令洞值为新值,完成插入操作

}

既然是max-heap,最大值必然在根节点.pop操作取走根节点.为满足complete binary tree的条件,必须割舍最下层
最右边的叶子节点,并将其值重新安插至max-heap.

//下面是pop-heap算法的实现细节.该函数接受两个迭代器,用来表示一个heap底部容器(vector)的头尾.

template <class RandomAccessIterator >
inline void pop_heap(RandomAccessIterator first,RandomAccessIterator last)
{
	__pop_heap_aux(first,last,value_type(first));
}
template<class RandomAccessIterator,class T>
inline void __pop_heap_aux(RandomAccessIterator first,RandomAccessIterator last,T*)
{
	__pop_heap(first,last-1,last-1,T(*(last-template <class RandomAccessIterator >
inline void pop_heap(RandomAccessIterator first,RandomAccessIterator last)
{
	__pop_heap_aux(first,last,value_type(first));
}
template<class RandomAccessIterator,class T>
inline void __pop_heap_aux(RandomAc1)),distance_type(first));

//根据heap的次序特性,pop操作的结果应为底部容器的第一个元素,因此,首先设定欲调整值为尾值,然后将
//首值调整至尾节点,(所以以上将迭代器result设为last-1)
}
//以下这组__pop_heap()不允许指定"大小比较标准"
template<class RandomAccessIterator,class T,class Distance>
inline void __pop_heap(RandomAccessIterator first,RandomAccessIterator last,RandomAccessIterator result,T value,Distance*)
{
	*result=*first;//设定尾值为首值,于是尾值就是欲求结果,可由客户端稍后再以底层容器之pop_back()取出尾值
	__adjust_heap(first,Distance(0),Distance(last-first),value);
	//以上欲重新调整heap,洞号为0(也就是树根出),欲调整值为value(原尾值)
}
//一下这个__adjust_heap()不允许指定"大小比较标准"
template <class RandomAccessIterator ,class Distance,class T>
void __adjust_heap(RandomAccessIterator first,Distance holeIndex,Distance len,T value)
{
	Distance topIndex=holeIndex;
	Distance secondChild=2*holeIndex+2;//洞节点之右子节点
	while(secondChild<len){
		//比较洞节点之左右两个子值,然后以secondChild代表较大的子结点
		if(*(first+secondChild)<(first+(secondChild-1)))
			secondChild--;
		//令较大子值为洞值,再令洞号下移至较大子节点处
		*(first+holeIndex)=*(first+secondChild);
		holeIndex=secondChild;
		//找出新洞结点的右子结点
		secondChild=2*(secondChild+1);
}

		if(secondChild==len){//没有右子结点 只有左子结点
		//令左子值为洞值,再令洞号下移至左子结点处
		*(first+holeIndex)=*(first+(secondChild-1));
		holeIndex=secondChild-1;
		
}
	__push_heap(first,holeIndex,topIndex,value);
}

注意pop_heap之后,最大元素只是被放置于底部容器最尾端,尚未被取走.如果要取走其值,可用容器底部(vector)所提供的back()操作函数.如果要
//移除它,可使用底部容器(vector)所提供的pop_back()函数

既然每次pop_heap可获得heap键中最大的元素,如果持续对整个heap做pop_heap操作,每次操作范围从后向前缩减一个元素
因为pop_heap会把键值最大的元素放在底部容器的最尾端 当整个程序执行完毕的时候,我们便有了一个递增序列
注意 排序过后,原来的heap就不再是一个合法的heap了

//以下这个sort_heap()不允许指定"大小比较标准"
template<class RandomAccessIterator first,RandomAccessIterator last>
void sort_heap(RandomAccessIterator first,RandomAccessIterator last){
	//以下,每执行一次pop_heap().极值就被放到了最尾端
	//扣除尾端在执行一次pop_heap(),次极值又被放在了尾端
	//一直下去,最后得到排序结果
	while(last-first>1)
		pop_heap(first,last--);//每执行pop_heap一次,操作范围即退缩一格

}

//这个算法用来将一段现有的数据转化为一个heap
//将[first,last)排列成为一个heap

template<class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first,RandomAccessIterator last)
{
	__make_heap(first,last,value_type(first),distance_type(first));
}
//一下这组make_heap()不允许指定"大小比较标准"
template <class RandomAccessIterator ,class T,class Distance>
void __make_heap(RandomAccessIterator first,RandomAccessIterator last,T*,Distance *)
{
	if(last-first<2) return;//如果长度为0或者是1,那么不必重新排列
	Distance len=last-first;
	//找出第一个不需要重排的子树头部,以parent标出
	Distance parent=(len-2)/2;
	while(true){
	//重排以parent为首的子树,len是为了让 __adjust_heap()判断操作范围
	__adjust_heap(first,parent,len,T(*(first+parent)));
	if (parent==0) return ;//走完根节点,结束
	parent--;
}
}

下面给出一个测试实例

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
{
	//test heap(底层以vecotr 完成)
	int ia[9]={0,1,2,3,4,8,9,3,5};
	vector<int>ivec(ia,ia+9);
	make_heap(ivec.begin(),ivec.end());
	for(int i=0;i<ivec.size();++i)
		{
	cout<<ivec[i]<<' ';//9 5 8 3 4 0 2 3 1
}
	cout<<endl;
	ivec.push_back(7);
	push_heap(ivec.begin(),ivec.end());
	for(int i=0;i<ivec.size();++i)
		cout<<ivec[i]<<' ';//9,7,8,3,5,0,2,3,1,4
	cout<<endl;	
	pop_heap(ivec.begin(),ivec.end());
	cout<<ivec.back()<<endl;
	ivec.pop_back();
	
	for(int i=0;i<ivec.size();++i)
		cout<<ivec[i]<<' ';
	cout<<endl;
	sort_heap(ivec.begin(),ivec.end());
	for(int i=0;i<ivec.size();++i)
		cout<<ivec[i]<<' ';
	cout<<endl;
}	
{
	//test heap 底层以array完成
	int ia[9]={0,1,2,3,4,8,9,3,5};
	make_heap(ia,ia+9);
	//array无法动态改变大小,因此不可以对满载的array进行push_heap()操作
	//因为那得现在array尾端增加一个元素,如果对一个满载的array执行
	//push_heap操作,该函数会将最后一个元素视为新增元素,并将其余元素视为
	//一个完整的heap结构 因此执行的结果等于原先的heap
	sort_heap(ia,ia+9);
	for(int i=0;i<9;++i)
		cout<<ia[i]<<' ';//0 1 2 3 4 5 6 7 8 9
	cout<<endl;//经过排序后的heap是一个不合法的heap 因为已经不满足完全二叉树
	//重新做一个heap
	make_heap(ia,ia+9);
	pop_heap(ia,ia+9);
	cout<<ia[8]<<endl;
}
{
	//test heap(底层以array实现)
	int ia[6]={4,1,7,6,2,5};
	make_heap(ia,ia+6);
	for(int i=0;i<6;++i)
		cout<<ia[i]<<' ';
	cout<<endl;

}
return 0;
}