Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

建立一個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 <stdio.h>
#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;
}