資料結構中的堆的插入與刪除

在這裡，我們將瞭解如何從二叉堆資料結構中插入和刪除元素。假設初始樹形如下 −

插入演算法

insert(heap, n, item):
Begin
   if heap is full, then exit
   else
      n := n + 1
      for i := n, i > 1, set i := i / 2 in each iteration, do
         if item <= heap[i/2], then break
         heap[i] = heap[i/2]
      done
   end if
   heap[i] := item
End

示例

假設我們要將 30 插入堆中 −


刪除演算法

delete(heap, n):
Begin
   if heap is empty, then exit
   else
      item := heap[1]
      last := heap[n]
      n := n – 1
      for i := 1, j := 2, j <= n, set i := j and j := j * 2, do
         if j < n, then
            if heap[j] < heap[j + 1], then j := j + 1
         end if
         if last >= heap[j], then break
         heap[i] := heap[j]
      done
   end if
   heap[i] := last
End

示例

假設我們要從最終的堆中刪除 30 −

更新日期: 2020 年 8 月 10 日

5 千次瀏覽

開啟你的 職業生涯

獲取課程結業證書

開始學習
廣告