堆的具體操作
堆的定義： 二叉樹(shù)中的父節(jié)點(diǎn)均小于或者等于子節(jié)點(diǎn)的值。
若h(1,n-1)是堆，若添加了一個(gè)元素置n處，則并不一定能保持堆得性質(zhì)，所以需要進(jìn)行移動(dòng)元素，這就需要函數(shù)siftup() ，
將新添加的元素，向上移動(dòng)，將父節(jié)點(diǎn)移到下部。
具體代碼如下：
/**//*
調(diào)整堆排序
堆的特點(diǎn)：子節(jié)點(diǎn)均大于或者等于父節(jié)點(diǎn)
*/
#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 插入前的數(shù)組個(gè)數(shù)
*/
void siftup(int * a , int n )
{
int i = n , j;
while(1)
{
if(i == 1 )
break ;
j = i >> 1 ; //父節(jié)點(diǎn)在數(shù)組中的存儲(chǔ)位置
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]) //這個(gè)設(shè)計(jì)巧妙
j++ ;
if(a[i] > a[j])
{
Swap(a[i] , a[j]) ;
i = j ;
}
else
return ;
}
else
return ;
}
四 求堆中的最小值
堆的最小值即為堆頂?shù)闹担唧w做法為先取頂點(diǎn)值，然后將堆尾的值移動(dòng)到堆頂，然后執(zhí)行siftdown()函數(shù)，重新初始化堆。
void getMin(int * a , int n)
{
int t = a[1] ;
a[1] = a[n] ;
siftdown(a , --n) ;
}
五 堆排序：
對(duì)所有的元素使用insert方法，插入在隊(duì)尾，然后調(diào)用siftup()方法，調(diào)整。
將所有的元素放入堆中之后，調(diào)用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) ;
}
六 總結(jié)
實(shí)質(zhì)上本文主要講解了堆排序算法，首先將每一個(gè)元素加入數(shù)組尾部，然后調(diào)用siftup()函數(shù)逐步上調(diào)，循環(huán)n次該過(guò)程。
插入完畢之后，每次從隊(duì)首取出最小元素，然后將隊(duì)尾元素移動(dòng)到堆頭，調(diào)用siftdown()函數(shù)，使元素下移，恢復(fù)堆屬性。
整個(gè)堆排序?yàn)镺（n*logn）。