heap sort

請利用堆積排序法(heap sort)進行以下數值的排序(需寫出完整步驟)。

5, 4, 1, 8, 3, 2, 7

因為不是本科系,想跨科考計概,但是這題目雖然書上有寫卻是一知半解,希望有人能給我詳解,感激不敬!

Update:

補充一點,我要的不是程式,是要樹狀圖根解法解說唷,感謝您熱情的回答!

Update 2:

如果以設為MAX-HEAP

(A) 5 (B) 8

/ \ ------> / \

4 1 5 1

/ / \ / \

8 4 3 2 7

Update 3:

上面亂掉了,總之感謝妳,不過我認為您PPT內以MIN為解的答案不太正確@@!

2 Answers

Rating
  • 1 decade ago
    Favorite Answer

    維基找到相關的資料:

    http://zh.wikipedia.org/zh-tw/堆排序

    Google到的網站:

    http://caterpillar.onlyfun.net/Gossip/AlgorithmGos...

    其實就是利用二元樹定義一個陣列,然後想辦法利用二元樹原具有的關係搞出個排序。不過詳細一點內容我可能要晚一點再看。

    PS:其他的排序法:

    http://zh.wikipedia.org/wiki/排序算法

    2010-01-28 00:38:44 補充:

    先用意見回答,明天再整理

    http://w10.loxa.com.tw/s37185622/share/headsort.ht...

    2010-01-29 19:25:48 補充:

    1. 將二元樹定義在陣列上。

    2. 二元樹根位於陣列上的第1個位置(第0個位置放著沒用)

    從程式碼中可看到以下幾項:

    /*堆積排序(傳入將要排序的陣列及其陣列大小) */

    void HeapSort(int A[], int size);

      

      //單一子結點最大堆積樹調整

    void Max_Heapify(int A[], int index, int size);

      

      //建立最大堆積樹(讓上層值比下層值大)

    void Build_Max_Heap(int A[], int size);

      

      //在螢幕上印出此二元樹陣列的內容 (不印出元素0)

    void print_tree(int A[], int size);

      

    //PS: 陣列形式的二元樹,元素0是放著不用的

    //*******************************************

    Max_Heapify:單一子結點最大堆積樹調整

    讓指定的節點值,下沉到正確的層級(比上層值小,比下層值大)。

    堆積排序時有兩個步驟:

    1. 建立最大堆積樹(Build_Max_Heap):

    由底層到高層依序進行Max_Heapify,讓上層值比下層值大。

    2. 為值定位

    經上步驟後,最上層肯定是最大值,隱藏(或說限制)Max_Heapify所能調整的範圍,而隱藏的部分就是放已排序後值的地方,藉由不停的交換及Max_Heapify調整,可依序將此數列排序完成。

    詳細排序過程請看ppt: headsort.ppt

    程式碼: headsort.htm ( HTML clipboard 更新日期:2010/1/29,看不到請重新整理)

    PS: 以上很多部份純屬我本身的見解,如有錯誤或疑問可以寄信給我~

    2010-01-30 11:38:41 補充:

    哪裡不正確要講清楚阿... 丟下一句話就要了結嗎?

    2010-02-01 19:44:10 補充:

    首先,我為我的話說聲抱歉,

    不過依舊有問題

    1. 這是公開網站,是個知識+,並不是沒有人會再看到,你要曉得,別人是會搜尋到!會看到!會參考到! 知識+並不是只有點數

    2. 沒錯!你是說了"認為"兩個字,但然後呢? 任何只說"認為"的話都沒有任何意義;質疑我的看法有錯固然不是錯!,但麻煩提出你的看法及依據!

    3. 一般情況下,結案是沒有問題的;可是當問題還是存在就直接結案,這本身就有問題! 這裡還有其他人可能會回答,這樣草率結案並不是明智的選擇。

    在這邊很感謝你的回覆,也歡迎下次再來知識+問問題。

  • 1 decade ago

    我有補充說了不要程式你還是給我程式,我要的是你PP裡面的那過程,可是最後答案跟我看書的內容不一樣,我是發問者你是解答者,我對這題已經找到我想要的答案了,我也很感謝你的用心跟上網搜尋資料,況且你也說很多是"你"個人的看法,我也說"我"認為不對,至於真正的答案是什麼我不知道,但是我看書加上你搜尋的資料已經理解解法了,所以我給了你獎勵的20點結了它,請問這樣有哪裡錯?請您以後發言口氣好一點好嗎?感謝您的用心!

Still have questions? Get your answers by asking now.