堆的定義:
n個(gè)關(guān)鍵字序列Kl,,K2,,…,Kn稱為堆,,當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡稱為堆性質(zhì)): (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤) 若將此序列所存儲(chǔ)的向量R[1..n]看做是一棵完全二叉樹的存儲(chǔ)結(jié)構(gòu),,則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹:樹中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字。 堆的這個(gè)性質(zhì)使得可以迅速定位在一個(gè)序列之中的最小(大)的元素. 堆排序算法的過程如下:1)得到當(dāng)前序列的最小(大)的元素 2)把這個(gè)元素和最后一個(gè)元素進(jìn)行交換,這樣當(dāng)前的最小(大)的元素就放在了序列的最后,而原先的最后一個(gè)元素放到了序列的最前面 3)的交換可能會(huì)破壞堆序列的性質(zhì)(注意此時(shí)的序列是除去已經(jīng)放在最后面的元素),因此需要對(duì)序列進(jìn)行調(diào)整,使之滿足于上面堆的性質(zhì).重復(fù)上面的過程,直到序列調(diào)整完畢為止.
before Heap sort: 71 18 151 138 160 63 174 169 79 78 // 開始調(diào)整前半段數(shù)組元素 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 // 開始進(jìn)行全局的調(diào)整 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 //*****************************************
/*
Name: 堆排序算法 Author: zhuqing
Des cription: 堆排序算法的過程演示 Date: 18-08-03 09:50 Copyright: */ #include<stdio.h>
#define N 6 int k,j; /* 建堆函數(shù) */ 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; } } /* 打印數(shù)組函數(shù) */ void prnt(int *a,int n){ int i; printf("\n"); for(i=0;i<n;i++){ printf("%3d",a[i]); } printf("\n"); } /* 打印堆函數(shù) */ 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; } /* 打印已排序數(shù)組函數(shù) */ 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 請(qǐng)輸入待排序數(shù)組個(gè)數(shù),以回車結(jié)束:\n"); scanf("%3d",&len); printf("\n 請(qǐng)輸入待排序數(shù)組,以回車結(jié)束:\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 初始數(shù)組: \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 排序結(jié)果:\n"); prnt(a,len); printf("\n============================================\n\n"); getch(); } //*****************************************************************
堆排序簡介: 堆排序在最壞的情況下,,其時(shí)間復(fù)雜度也能達(dá)到O(nlogn),。相對(duì)于快速排序來說,這是它最大的優(yōu)點(diǎn),,此外,,堆排序僅需要一個(gè)記錄大小供交換用的輔助存儲(chǔ)空間。 堆排序的數(shù)據(jù)結(jié)構(gòu)是二叉堆,,二叉堆的特點(diǎn)有兩個(gè),,一個(gè)是它是一棵完全二叉樹,另一個(gè)是它的根結(jié)點(diǎn)小于孩子結(jié)點(diǎn),,所以我們很容易找到它的最小結(jié)點(diǎn)----根結(jié)點(diǎn),;當(dāng)然如果你想找到最大結(jié)點(diǎn)的話,那就要掃描所有的葉子結(jié)點(diǎn),,這是很費(fèi)時(shí)間的,,如果你想找的是最大結(jié)點(diǎn)的話,你最好把它弄成一個(gè)大頂堆,,即一棵根結(jié)點(diǎn)大于孩子結(jié)點(diǎn)的完全二叉樹,。 二叉堆通常用數(shù)組來實(shí)現(xiàn),它舍棄下標(biāo)0,,從下標(biāo)1開始置數(shù),,則很容易滿足,對(duì)于數(shù)組中任意位置i上的元素,,其左兒子的位置在2i上,,右兒子的位置在2i+1上,雙親的位置則在i/2上,。 堆排序的算法之一是把數(shù)組構(gòu)建成二叉堆----這只要增添一個(gè)長度為n+1的輔助空間,然后把原數(shù)組的元素依次插入到二叉堆即可,。然后刪除二叉堆的根,,把它作為排序后的數(shù)組的第一個(gè)元素,然后使二叉堆的長度減1,并通過上移使得新得到的序列仍為二叉堆,再提取新二叉堆的第一個(gè)元素到新數(shù)組,。依此類推,,直到提取最后一個(gè)元素,新得到的數(shù)組就是排序后的數(shù)組,。 堆排序在最壞的情況下,,其時(shí)間復(fù)雜度也能達(dá)到O(nlogn)。相對(duì)于快速排序來說,,這是它最大的優(yōu)點(diǎn),,此外,堆排序僅需要一個(gè)記錄大小供交換用的輔助存儲(chǔ)空間,。 堆排序的數(shù)據(jù)結(jié)構(gòu)是二叉堆,,二叉堆的特點(diǎn)有兩個(gè),一個(gè)是它是一棵完全二叉樹,,另一個(gè)是它的根結(jié)點(diǎn)小于孩子結(jié)點(diǎn),,所以我們很容易找到它的最小結(jié)點(diǎn)----根結(jié)點(diǎn);當(dāng)然如果你想找到最大結(jié)點(diǎn)的話,,那就要掃描所有的葉子結(jié)點(diǎn),,這是很費(fèi)時(shí)間的,如果你想找的是最大結(jié)點(diǎn)的話,,你最好把它弄成一個(gè)大頂堆,,即一棵根結(jié)點(diǎn)大于孩子結(jié)點(diǎn)的完全二叉樹。 二叉堆通常用數(shù)組來實(shí)現(xiàn),,它舍棄下標(biāo)0,,從下標(biāo)1開始置數(shù),則很容易滿足,,對(duì)于數(shù)組中任意位置i上的元素,,其左兒子的位置在2i上,右兒子的位置在2i+1上,,雙親的位置則在i/2上,。 堆排序的算法之一是把數(shù)組構(gòu)建成二叉堆----這只要增添一個(gè)長度為n+1的輔助空間,然后把原數(shù)組的元素依次插入到二叉堆即可,。然后刪除二叉堆的根,把它作為排序后的數(shù)組的第一個(gè)元素,然后使二叉堆的長度減1,,并通過上移使得新得到的序列仍為二叉堆,,再提取新二叉堆的第一個(gè)元素到新數(shù)組。依此類推,,直到提取最后一個(gè)元素,,新得到的數(shù)組就是排序后的數(shù)組。 根據(jù)要求實(shí)現(xiàn)程序如下: #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; }
堆排序的空間復(fù)雜度要求O(1),上面程序使用了輔助數(shù)組,,所以其空間復(fù)雜度為O(n),,不符合要求,所以又寫了一個(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) { //構(gòu)建最小堆 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; } |
|