堆的定義:
n個(gè)關(guān)鍵字序列Kl，K2，…，Kn稱(chēng)為堆，當且僅當該序列滿(mǎn)足如下性質(zhì)(簡(jiǎn)稱(chēng)為堆性質(zhì))：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)
若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹(shù)的存儲結構，則堆實(shí)質(zhì)上是滿(mǎn)足如下性質(zhì)的完全二叉樹(shù)：樹(shù)中任一非葉結點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結點(diǎn)的關(guān)鍵字。
堆的這個(gè)性質(zhì)使得可以迅速定位在一個(gè)序列之中的最小(大)的元素.
堆排序算法的過(guò)程如下:1)得到當前序列的最小(大)的元素 2)把這個(gè)元素和最后一個(gè)元素進(jìn)行交換,這樣當前的最小(大)的元素就放在了序列的最后,而原先的最后一個(gè)元素放到了序列的最前面 3)的交換可能會(huì )破壞堆序列的性質(zhì)(注意此時(shí)的序列是除去已經(jīng)放在最后面的元素),因此需要對序列進(jìn)行調整,使之滿(mǎn)足于上面堆的性質(zhì).重復上面的過(guò)程,直到序列調整完畢為止.
- // array是待調整的堆數組,i是待調整的數組元素的位置,length是數組的長(cháng)度
- void HeapAdjust(int array[], int i, int nLength)
- {
- int nChild, nTemp;
- for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild)
- {
- // 子結點(diǎn)的位置是 父結點(diǎn)位置 * 2 + 1
- nChild = 2 * i + 1;
- // 得到子結點(diǎn)中較大的結點(diǎn)
- if (nChild != nLength - 1 && array[nChild + 1] > array[nChild])
- ++nChild;
- // 如果較大的子結點(diǎn)大于父結點(diǎn)那么把較大的子結點(diǎn)往上移動(dòng),替換它的父結點(diǎn)
- if (nTemp < array[nChild])
- {
- array[i] = array[nChild];
- }
- else // 否則退出循環(huán)
- {
- break;
- }
- }
- // 最后把需要調整的元素值放到合適的位置
- array[i] = nTemp;
- }
- // 堆排序算法
- void HeapSort(int array[], int length)
- {
- // 調整序列的前半部分元素,調整完之后第一個(gè)元素是序列的最大的元素
- for (int i = length / 2 - 1; i >= 0; --i)
- {
- HeapAdjust(array, i, length);
- }
- // 從最后一個(gè)元素開(kāi)始對序列進(jìn)行調整,不斷的縮小調整的范圍直到第一個(gè)元素
- for (int i = length - 1; i > 0; --i)
- {
- // 把第一個(gè)元素和當前的最后一個(gè)元素交換,
- // 保證當前的最后一個(gè)位置的元素都是在現在的這個(gè)序列之中最大的
- Swap(&array[0], &array[i]);
- // 不斷縮小調整heap的范圍,每一次調整完畢保證第一個(gè)元素是當前序列的最大值
- HeapAdjust(array, 0, i);
- }
- }
一個(gè)測試及輸出的結果,在每次HeapAdjust之后顯示出來(lái)當前數組的情況
before Heap sort:
71 18 151 138 160 63 174 169 79 78
// 開(kāi)始調整前半段數組元素
71 18 151 138 160 63 174 169 79 78
71 18 151 169 160 63 174 138 79 78
71 18 174 169 160 63 151 138 79 78
71 169 174 138 160 63 151 18 79 78
174 169 151 138 160 63 71 18 79 78
// 開(kāi)始進(jìn)行全局的調整
169 160 151 138 78 63 71 18 79 174
160 138 151 79 78 63 71 18 169 174
151 138 71 79 78 63 18 160 169 174
138 79 71 18 78 63 151 160 169 174
79 78 71 18 63 138 151 160 169 174
78 63 71 18 79 138 151 160 169 174
71 63 18 78 79 138 151 160 169 174
63 18 71 78 79 138 151 160 169 174
18 63 71 78 79 138 151 160 169 174
#include<stdio.h>
#define N 6
int k,j;
/* 建堆函數 */
void build(int *a,int i,int n){
int tmp;
k=i;
j=2*k+1;
while(j<=n){
if(j<n && a[j]<a[j+1])
j++;
if(a[k]>=a[j])break;
tmp=a[k];
a[k]=a[j];
a[j]=tmp;
k=j;
j=2*j+1;
}
}
/* 打印數組函數 */
void prnt(int *a,int n){
int i;
printf("\n");
for(i=0;i<n;i++){
printf("%3d",a[i]);
}
printf("\n");
}
/* 打印堆函數 */
void prnthp(int *a,int b1,int b2){
int size;
int h=0,sum=0,item=1;
int i,j,cnt,start,tmp;
size=b2-b1+1;
while(sum<=size){
sum+=item;
h++;
item*=2;
}
item=1;
cnt=0;
start=b1;
tmp=1;
printf("\n--------------------------------------------\n");
printf(" 堆：\n");
while(1){
for(i=0;i<h;i++){
for(j=0;j<h-i;j++)
printf(" ");
for(j=0;j<i+1;j++)printf(" ");
for(j=0;j<tmp;j++){
if(cnt>size-1)goto end;
printf("%4d",a[cnt++]);
}
printf("\n");
tmp*=2;
}
}
end:
printf("\n");
return;
}
/* 打印已排序數組函數 */
void prntar(int *a,int b2,int len){
int i;
printf(" 已排序：\n");
for(i=0;i<b2;i++){
printf(" ");
}
for(i=b2;i<=len;i++){
printf("%3d",a[i]);
}
printf("\n");
}
main(){
/* int a[]={-1,2,5,1,0,-3,-2,8,6}; */
int a[50];
int i;
int tmp;
int sum;
int num;
int len;
printf(" 堆排序\n");
printf("\n============================================\n");
printf("\n 請輸入待排序數組個(gè)數,以回車(chē)結束：\n");
scanf("%3d",&len);
printf("\n 請輸入待排序數組,以回車(chē)結束：\n");
for(i=0;i<len;i++)
scanf("%3d",&a[i]);
tmp=1;sum=0;
while(sum+tmp<=len){
sum+=tmp;
tmp*=2;
}
printf("\n============================================\n");
printf("\n 初始數組： \n");
prnt(a,len);
/* 建初始堆 */
for(i=sum-1;i>=0;i--)
build(a,i,len-1);
prnthp(a,0,len-1);
/* 改建堆 */
for(i=0;i<len-1;i++){
tmp=a[0];
a[0]=a[len-1-i];
a[len-1-i]=tmp;
build(a,0,len-2-i);
prnthp(a,0,len-2-i);
prntar(a,len-1-i,len-1);
}
printf("\n--------------------------------------------\n");
printf("\n 排序結果：\n");
prnt(a,len);
printf("\n============================================\n\n");
getch();
}
堆排序簡(jiǎn)介：
堆排序在最壞的情況下，其時(shí)間復雜度也能達到O（nlogn）。相對于快速排序來(lái)說(shuō)，這是它最大的優(yōu)點(diǎn)，此外，堆排序僅需要一個(gè)記錄大小供交換用的輔助存儲空間。
堆排序的數據結構是二叉堆，二叉堆的特點(diǎn)有兩個(gè)，一個(gè)是它是一棵完全二叉樹(shù)，另一個(gè)是它的根結點(diǎn)小于孩子結點(diǎn)，所以我們很容易找到它的最小結點(diǎn)----根結點(diǎn)；當然如果你想找到最大結點(diǎn)的話(huà)，那就要掃描所有的葉子結點(diǎn)，這是很費時(shí)間的，如果你想找的是最大結點(diǎn)的話(huà)，你最好把它弄成一個(gè)大頂堆，即一棵根結點(diǎn)大于孩子結點(diǎn)的完全二叉樹(shù)。
二叉堆通常用數組來(lái)實(shí)現，它舍棄下標0，從下標1開(kāi)始置數，則很容易滿(mǎn)足，對于數組中任意位置i上的元素，其左兒子的位置在2i上，右兒子的位置在2i+1上，雙親的位置則在i/2上。
堆排序的算法之一是把數組構建成二叉堆----這只要增添一個(gè)長(cháng)度為n+1的輔助空間，然后把原數組的元素依次插入到二叉堆即可。然后刪除二叉堆的根，把它作為排序后的數組的第一個(gè)元素,然后使二叉堆的長(cháng)度減1，并通過(guò)上移使得新得到的序列仍為二叉堆，再提取新二叉堆的第一個(gè)元素到新數組。依此類(lèi)推，直到提取最后一個(gè)元素，新得到的數組就是排序后的數組。
堆排序在最壞的情況下，其時(shí)間復雜度也能達到O（nlogn）。相對于快速排序來(lái)說(shuō)，這是它最大的優(yōu)點(diǎn)，此外，堆排序僅需要一個(gè)記錄大小供交換用的輔助存儲空間。
堆排序的數據結構是二叉堆，二叉堆的特點(diǎn)有兩個(gè)，一個(gè)是它是一棵完全二叉樹(shù)，另一個(gè)是它的根結點(diǎn)小于孩子結點(diǎn)，所以我們很容易找到它的最小結點(diǎn)----根結點(diǎn)；當然如果你想找到最大結點(diǎn)的話(huà)，那就要掃描所有的葉子結點(diǎn)，這是很費時(shí)間的，如果你想找的是最大結點(diǎn)的話(huà)，你最好把它弄成一個(gè)大頂堆，即一棵根結點(diǎn)大于孩子結點(diǎn)的完全二叉樹(shù)。
二叉堆通常用數組來(lái)實(shí)現，它舍棄下標0，從下標1開(kāi)始置數，則很容易滿(mǎn)足，對于數組中任意位置i上的元素，其左兒子的位置在2i上，右兒子的位置在2i+1上，雙親的位置則在i/2上。
堆排序的算法之一是把數組構建成二叉堆----這只要增添一個(gè)長(cháng)度為n+1的輔助空間，然后把原數組的元素依次插入到二叉堆即可。然后刪除二叉堆的根，把它作為排序后的數組的第一個(gè)元素,然后使二叉堆的長(cháng)度減1，并通過(guò)上移使得新得到的序列仍為二叉堆，再提取新二叉堆的第一個(gè)元素到新數組。依此類(lèi)推，直到提取最后一個(gè)元素，新得到的數組就是排序后的數組。
根據要求實(shí)現程序如下：
#include <stdio.h>
void push_heap(int *array, int pos, int value)
{
int i;
for(i=pos; i/2>0 && array[i/2]>value; i/=2) {
array[i] = array[i/2];
}
array[i] = value;
}
void make_heap(int *data, int *array, int len)
{
for(int i=0; i<len; ++i) {
push_heap(array, i+1, data[i]);
}
}
int pop_heap(int *array, int last)
{
int value = array[1];
array[1] = array[last];
int i=1;
while(2*i < last) {
int min = array[2*i] < array[2*i+1] ? array[2*i] : array[2*i+1];
int pos = array[2*i] < array[2*i+1] ? (2*i) : (2*i+1);
if(array[i] > min) {
int tmp = array[i];
array[i] = min;
array[pos] = tmp;
i = pos;
}
}
return value;
}
void sort_heap(int *data, int *array, int len)
{
for(int i=0; i<len; ++i) {
data[i] = pop_heap(array, len-i);
}
}
int main()
{
int data[] = {12, 34, 23, 3, 1, 45, 87, 99};
int array[10];
make_heap(data, array, 8);
for(int i=1; i<=8; ++i) {
printf("%d ", array[i]);
}
printf("\n");
sort_heap(data, array, 8);
for(int i=0; i<8; ++i) {
printf("%d ", data[i]);
}
printf("\n");
return 0;
}
堆排序的空間復雜度要求O(1)，上面程序使用了輔助數組，所以其空間復雜度為O(n)，不符合要求，所以又寫(xiě)了一個(gè),如下：
#include <stdio.h>
int swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void adjust(int *array, int i, int n)
{
int min, pos;
while(1) {
if((2*i+2) < n) {
min = array[2*i+1] < array[2*i+2] ? array[2*i+1] : array[2*i+2];
pos = array[2*i+1] < array[2*i+2] ? (2*i+1) : (2*i+2);
if(array[i] < min) { break; }
swap(&array[i], &array[pos]);
i = pos;
} else if((2*i+2) == n) {
min = array[2*i+1];
pos = 2*i+1;
if(array[i] < min) { break; }
swap(&array[i], &array[pos]);
i = pos;
} else {
break;
}
}
}
void heap_sort(int *array, int n)
{
//構建最小堆
for(int j=(n-1)/2; j>=0; --j) {
adjust(array, j, n);
}
//降序排列
for(int i=n; i>1; --i) {
swap(&array[0], &array[i-1]);
adjust(array, 0, --n);
}
}
int main()
{
int data[] = {12, 34, 23, 3, 1, 45, 87, 99};
heap_sort(data, 8);
for(int i=0; i<8; ++i) {
printf("%d ", data[i]);
}
printf("\n");
return 0;
}
