堆的具体操作
堆的定义： 二叉树中的父节点均小于或者等于子节点的值。
若h(1,n-1)是堆，若添加了一个元素置n处，则并不一定能保持堆得性质，所以需要进行移动元素，这就需要函数siftup() ，
将新添加的元素，向上移动，将父节点移到下部。
具体代码如下：
/**//*
调整堆排序
堆的特点：子节点均大于或者等于父节点
*/
#include <iostream>
using namespace std ;
inline void Swap(int & x , int &y) ;
void siftup(int * a , int n) ;
int main()
{
int a [] = {-1 ,12 , 20 , 15 , 29 ,23 ,17 , 22 , 35 , 40 , 26 , 51 ,19 , 13} ;
siftup(a , 13) ;
for(int i = 0 ; i < 14 ; i++)
{
cout<<a[i]<<" " ;
}
cin.get();
return 0 ;
}
inline void Swap(int & x , int &y)
{
int temp = x ;
x = y ;
y = temp ;
}
/**//*
x 表示待插入的元素
n 插入前的数组个数
*/
void siftup(int * a , int n )
{
int i = n , j;
while(1)
{
if(i == 1 )
break ;
j = i >> 1 ; //父节点在数组中的存储位置
if(a[j] > a[i])
{
Swap(a[j] , a[i]) ;
i = j ;
} else
{
break ;
}
}
}
三 下移操作
void siftdown(int * a , int n)
{
int i = 1 ;
while(i <= n )
{
int j = i << 1 ;
if(j > n)
return ;
if(j + 1 <= n)
{
if(a[j + 1] < a[j]) //这个设计巧妙
j++ ;
if(a[i] > a[j])
{
Swap(a[i] , a[j]) ;
i = j ;
}
else
return ;
}
else
return ;
}
四 求堆中的最小值
堆的最小值即为堆顶的值，具体做法为先取顶点值，然后将堆尾的值移动到堆顶，然后执行siftdown()函数，重新初始化堆。
void getMin(int * a , int n)
{
int t = a[1] ;
a[1] = a[n] ;
siftdown(a , --n) ;
}
五 堆排序：
对所有的元素使用insert方法，插入在队尾，然后调用siftup()方法，调整。
将所有的元素放入堆中之后，调用getMin()方法，即完成了堆排序算法。
for(int i = 1 ; i < n ; i++)
{
siftup(a , i) ;
}
for(int i = 1 ; i < n ; i++)
{
cout<<a[1]<<" " ;
getMin(a , n-i) ;
}
六 总结
实质上本文主要讲解了堆排序算法，首先将每一个元素加入数组尾部，然后调用siftup()函数逐步上调，循环n次该过程。
插入完毕之后，每次从队首取出最小元素，然后将队尾元素移动到堆头，调用siftdown()函数，使元素下移，恢复堆属性。
整个堆排序为O（n*logn）。