堆的具體操作
堆的定義： 二叉樹中的父節點均小于或者等于子節點的值。
若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）。