最小—最大堆積
| 最小—最大堆 | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 類型 | 二叉樹/堆 | ||||||||||||
| 發明時間 | 1986 | ||||||||||||
| 用大O符號表示的時間複雜度 | |||||||||||||
| |||||||||||||
最小—最大堆（Min-Max Heap）是最大層和最小層交替出現的二叉樹，即最大層結點的子節點屬於最小層，最小層結點的子節點屬於最大層。以最大（小）層結n點為根結點的子樹保有最大（小）堆性質：根結點的鍵值為該子樹結點鍵值中最大（小）項。
介紹
[編輯]- 最大堆：根結點的鍵值是所有堆結點鍵值中最大者的堆。
- 最小堆：根結點的鍵值是所有堆結點鍵值中最小者的堆。
而最大—最小堆集結了最大堆和最小堆的優點，這也是其名字的由來。