2012-12-30 13:45:56Morris
[資料結構][作業] Heap Sort
建立一個Max-Heap
heap建構方法使用Bottom-Up(使用Top-down而造成level order不同的話視為
輸出錯誤)
輸入格式跟作業3一樣用動態讀取
然後請輸出Level Order和Heap Sort，例如:
Sample Input:
3 5 2 7 4 8 6
Sample Output:
Level Order:8 7 6 5 4 2 3
Heap Sort:2 3 4 5 6 7 8
(請參考附件的sample檔)
PS:
1.助教會使用其他測資來測試
2.請注意，使用function時請include該function所屬的library，否則若發生
compile error一律視同無法執行(即0分)，eg:使用scanf要include<stdio.h>
繳交期限:
2012/12/27 22:00
超過期限者每多一天扣作業分數10%
超過2012/12/31 22:00後繳交一律不給分。
#include <stdlib.h>
#include <sstream>
using std::stringstream;
void swap(int& x, int& y) {
static int t;
t = x, x = y, y = t;
}
void siftdown(int a[], int p, int n) {
static int s;
s = p<<1;
while(s <= n) {
if(s < n && a[s+1] > a[s]) s++;
if(a[p] >= a[s]) return;
swap(a[p], a[s]), p = s, s = p<<1;
}
}
void heapify(int a[], int n) {
int s, p;
s = n/2;
while(s) {
siftdown(a, s, n);
s--;
}
}
void heapsort(int a[], int n) {
heapify(a, n);
//<output1>
printf("Level Order: ");
for(int i = 1; i <= n; i++)
printf("%d ", a[i]);
puts("");
//</output1>
for(int i = n; i >= 2; i--) {
swap(a[1], a[i]);
siftdown(a, 1, i-1);
}
//<output2>
printf("Heap Sort : ");
for(int i = 1; i <= n; i++)
printf("%d ", a[i]);
puts("");
//</output2>
}
int main() {
int A[10001], n = 1;
printf("輸入數列 用空白隔開 : ");
char buf[32767];
gets(buf);
stringstream sin(buf);
while(sin >> A[n])
n++;
heapsort(A, n-1);
system("pause");
return 0;
}
下一篇：塊狀鏈表(初版)