#include<stdlib.h>	
#include<iostream.h>
/*
template<class T>//方法1
void BuildHeap(T* pa,int size)	//建堆
{for(int i=size/2-1;i>=0;i--)	//从邻近叶子的第一个非叶子结点至根节点PercolateDown(pa,i,size);	//向下调整为堆
}template<class T>
void PercolateDown(T* pa,int pos,int size)	//将[pos,size)范围内的数据向下调整为堆
{int p=pos,c=2*p+1;T temp=pa[p];while(c<size){if(c+1<size&&pa[c+1]>pa[c])	//取孩子结点中的最大值++c;if(temp>=pa[c])break;else{pa[p]=pa[c];//孩子结点大就向上移动p=c;c=2*p+1;	//向下循环}}pa[p]=temp;
}template<class T>
void HeapSort1(T* pa,int n)		//堆排序
{T temp;BuildHeap(pa,n);	//建大根堆for(int i=n-1;i>0;i--){temp=pa[0];			//首尾交换pa[0]=pa[i];pa[i]=temp;PercolateDown(pa,0,i);//将[pos,size)范围内的数据向下调整为堆}
}
*/
template<class T>//方法2
void PercolateUp(T* pa,int pos)		//从下标为pos的元素开始向上调整为堆
{int c=pos,p=(c-1)/2;T temp=pa[c];while(c>0)if(pa[p]>temp)break;else{pa[c]=pa[p];	//小就下移c=p;p=(c-1)/2;	//向上循环}pa[c]=temp;
}
template<class T>		//将[0,size)范围内的数据向下调整为堆
void PercolateDown(T* pa,int size)
{int p=0,c=2*p+1;T temp=pa[p];while(c<size){if(c+1<size&&pa[c+1]>pa[c])++c;if(temp>pa[c])break;else{pa[p]=pa[c];	//大就上移p=c;c=2*p+1;	//向下循环}}pa[p]=temp;
}
template<class T>
void BuildHeap(T* pa,int size)	//从第2个元素开始向上调整为堆
{for(int i=1;i<size;i++)PercolateUp(pa,i);
}
template<class T>
void HeapSort2(T* pa,int n)
{BuildHeap(pa,n);T temp;for(int i=n-1;i>0;i--){temp=pa[0];			//首尾交换pa[0]=pa[i];pa[i]=temp;PercolateDown(pa,i);//将[0,i)范围内的数据向下调整为堆}
}int main()
{int a[10]={7,6,5,4,3,2,1,9,8,10};
//	HeapSort1(a,10);//方法1HeapSort2(a,10);//方法2for(int i=0;i<10;i++)cout<<a[i]<<'\t';return 0;
}
//Heap.cpp
#include"Heap.h"
Heap::Heap(int max=100)array(100),size(0){}Heap::Heap(const Vector<T>& vt):array(vt.Size()+10),size(vt.Size())
{for(int i=0;i<vt.Size();++i)array[i]=vt[i];buildHeap();
}void Heap::buildHeap(void)
{for(int i=size/2-1;i>=0;i--)PercolateDown(i);
}