跳至內容

最小—最大堆積

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
最小—最大堆
類型二叉樹/堆
發明時間1986
大O符號表示的時間複雜度
算法 平均 最差
插入 O(log n) O(log n)
刪除 O(log n) [1] O(log n)
完全最大堆示例
完全最小堆示例

最小—最大堆Min-Max Heap)是最大層和最小層交替出現的二叉樹,即最大層結點的子節點屬於最小層,最小層結點的子節點屬於最大層。以最大(小)層結n點為根結點的子樹保有最大(小)堆性質:根結點的鍵值為該子樹結點鍵值中最大(小)項。

介紹

[編輯]

最大堆最小堆二叉堆的兩種形式。

  • 最大堆:根結點的鍵值是所有堆結點鍵值中最大者的堆。
  • 最小堆:根結點的鍵值是所有堆結點鍵值中最小者的堆。

而最大—最小堆集結了最大堆和最小堆的優點,這也是其名字的由來。

應用

[編輯]

參考文獻

[編輯]
  1. ^ Mischel. Jim. Stack Overflow. [8 September 2016].