数据结构 | 堆排序

#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);//方法1
	HeapSort2(a,10);//方法2
	for(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);
}

?

?