最（大）小堆的性质：
（1）是一颗完全二叉树，遵循完全二叉树的所有性质。
（2）父节点的键值（大于）小于等于子节点的键值
（3）在堆排序中我们通常用的是最大堆，最小堆通常用在优先队列中（尚未找到恰当的例子）。
堆排序：
数组：a[10]={16,14,10,8,7,9,3,2,4,1}可以利用建堆的方式对其进行排序。因为堆是一颗完全二叉树，根据完全二叉树的性质可以得知：对数组进行建堆之后，给定任意下标节点其父节点下标PARENT（i）=i/2 (取下整数)。左孩子下标为LEFT（i）=2*i 。右孩子下标为RIGHT（i）=2*i+1.如下图所示
堆排序代码见如下：
#include<iostream>
using namespace std;
//获取父节点
int Parent(int i)
{
return i/2;
}
//获取左孩子
int Left(int i)
{
return 2*i;
}
//获取右孩子
int Right(int i)
{
return 2*i+1;
}
//从i节点开始生成最大堆
void MaxHeap(int *a,int i,int length)
{
int L,R;
L=Left(i);
R=Right(i);
int largest;
if(L<=length&&a[L-1]>a[i-1])
{
largest=L;
}
else
largest=i;
if(R<=length&&a[R-1]>a[largest-1])
{
largest=R;
}
if(largest!=i)
{
int temp;
temp=a[i-1];
a[i-1]=a[largest-1];
a[largest-1]=temp;
MaxHeap(a,largest,length);
}
}
//将整个树生成最大堆
void Build_Max_Heap(int *a,int length)
{
//从length/2开始是因为length/2节点以下的都是叶子节点
for(int i=length/2;i>=1;i--)
{
MaxHeap(a,i,length);
}
}
//堆排序
void HeapSort(int *a,int length)
{
Build_Max_Heap(a,length);
int number=length;
for(int i=length;i>0;i--)
{
int temp;
temp=a[i-1];
a[i-1]=a[0];
a[0]=temp;
length-=1;
MaxHeap(a,1,length);
}
}
int main()
{
int a[10]={4,1,3,2,16,9,10,14,8,7};
HeapSort(a,10);
for(int i=0;i<10;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
利用最小堆对数组进行排序的实现代码如下：
#include<iostream>
using namespace std;
template<typename Type>class MinHeap
{
private:
Type *heap;
static const int defaultsize=1000;
int MaxSize;
int currentsize;
public:
MinHeap<Type>(int size)
{
currentsize=0;
Maxsize=defaultsize>size?size:defaultsize;
}
MinHeap<Type>(Type a[],int n);
bool Insert(Type n);
bool IsFull()
{
return currentsize==MaxSize;
}
bool IsEmpty()
{
return currentsize==0;
}
bool Delete(Type n);
void Adjust(int start,int n);
void Print();
void Sorte();
};
template<typename Type> MinHeap<Type>::MinHeap(Type a[], int n)
{
MaxSize=defaultsize>n?n:defaultsize;
currentsize=MaxSize;
heap=new Type[MaxSize];
for(int i=0;i<MaxSize;i++)
{
heap[i]=a[i];
}
int temp=(MaxSize-2)/2;
for(int i=temp;i>=0;i--)
{
Adjust(i,currentsize);
}
}
template<typename Type>bool MinHeap<Type>::Insert(Type n)
{
if(currentsize==MaxSize)
{
cout<<"the heap is full!"<<endl;
}
heap[currentsize]=n;
int j=currentsize;
while(j>0)
{
int P=j/2-1;
if(heap[P]<heap[j])
break;
int temp;
temp=heap[P];
heap[P]=heap[currentsize];
heap[currentsize]=temp;
j=P;
}
currentsize++;
return 1;
}
template<typename Type>bool MinHeap<Type>::Delete(Type n)
{
if(currentsize==0)
{
cout<<"this heap is empty!"<<endl;
}
bool flag=0;
for(int i=0;i<currentsize;i++)
{
if(heap[i]==n)
{
flag=1;
heap[i]=heap[currentsize-1];
Adjust(i,currentsize-2);
currentsize--;
i=0;
}
if(i==currentsize-1&&flag==0)
{
cout<<"there is no this element!"<<endl;
}
}
return 1;
}
template<typename Type>void MinHeap<Type>::Print()
{
for(int i=0;i<currentsize;i++)
{
cout<<heap[i]<<" ";
}
cout<<endl;
}
template<typename Type>void MinHeap<Type>::Adjust(int start, int n)
{
int L,R,min;
L=start*2+1;
R=L+1;
if(heap[start]>heap[L]&&L<n)
{
min=L;
}
else
min=start;
if(heap[min]>heap[R]&&R<n)
{
min=R;
}
if(start!=min)
{
int temp;
temp=heap[start];
heap[start]=heap[min];
heap[min]=temp;
Adjust(min,n);
}
}
template<typename Type>void MinHeap<Type>::Sorte()
{
int num=currentsize;
for(int i=currentsize-1;i>0;i--)
{
int temp;
temp=heap[i];
heap[i]=heap[0];
heap[0]=temp;
num-=1;
Adjust(0,num);
}
}
int main()
{
int init[30]={17,6,22,29,14,0,21,13,27,18,2,28,8
,26,3,12,20,4,9,23,15,1,11,5,19,24,16,7,10,25};
MinHeap<int> heape(init,30);
heape.Print();
cout<<endl<<endl<<endl;
heape.Insert(20);
heape.Print();
cout<<endl<<endl<<endl;
heape.Delete(20);
heape.Sorte();
heape.Print();
cout<<endl<<endl<<endl;
return 0;
}