asked in 電腦與網際網路程式設計 · 1 decade ago

有人會資料結構Binary Min-Heap嗎?

(a)Suppose that we have implemented a binary heap using a linear array

with the following keys 10,30,20,40,45,35,25,60,50.Draw the result

of inserting 27,17 and 7 into the heap.

(b)Draw the result after calling DeleteMin operation three times in the

heap obtained from(a).

(c)Suppose that we take the following keys as input:150,80,40,30,10,70,

110,100,20,90,60,50,120,140,130.Draw the resulting heap when the

linear-time algorithm BuildHeap is performed.

1 Answer

Rating
  • 1 decade ago
    Favorite Answer

    Min-Heap相關知識請至下面兩個網頁查閱

    http://www.cs.nchu.edu.tw/~fileman/notepad/ds05.ht...

    http://tw.knowledge.yahoo.com/question/?qid=100711...

    (a)原本的Min-Heap

              10

           /     \

          30       20

        /  \     / \

       40    45   35   25

      / \ 

     60   50

    加入27

              10

           /     \

          30       20

        /  \     / \

       40    45   35   25

      / \  /

     60   50 [候選]

              10

           /     \

          27       20

        /  \     / \

       40    30   35   25

      / \  / \

     60   50 45 [候選]

    加入17

              10

           /     \

          17       20

        /  \     / \

       40    27   35   25

      / \  / \ /

     60   50 45 30 [候選]

    加入7

              7

           /     \

          17       10

        /  \     / \

       40    27   20   25

      / \  / \ /

     60   50 45 30 35

    完成!!

    (b)刪除樹根3次

    請參考

    http://knight.fcu.edu.tw/~d9046876/ds/d_45.htm

    第一次刪除7,35上來補

              35

           /     \

          17       10

        /  \     / \

       40    27   20   25

      / \  / \

     60   50 45 30

    調整後

              10

           /     \

          27       17

        /  \     / \

       40    30   20   25

      / \  / \

     60   50 45 35

    完成圖

              27

           /     \

          35       30

        /  \     / \

       45    40   20   25

      / \ 

     60   50

    完成圖可能有錯誤,你可以自行推導比較!!~

    (c)linear-time algorithm你沒有說明,所以我直接畫圖

    加入40

              80

           /     \

          150      [候選]

    加入30

              40

           /     \

          150       80

        / 

       [候選]

    加入完成

               30

           /     \

          40       80

        / 

       150

    最後完成圖

              10

           /     \

          20       50

        /  \     / \

       30    40   70   110

      / \  / \ / \ / \

     150  100 90 60 80 120 140 130

    Source(s): 自己
Still have questions? Get your answers by asking now.