计算机科学

首页 > 计算机科学

最大—最小堆

2018-07-27 09:58:37     所属分类:数据结构
完全最大堆示例
完全最小堆示例

最大—最小堆是最大层和最小层交替出现的二叉树,即最大层结点的儿子属于最小层,最小层结点的儿子属于最大层。 以最大(小)层结n点为根结点的子树保有最大(小)堆性质:根结点的键值为该子树结点键值中最大(小)项。

目录

  • 1 介绍
  • 2 主要操作
    • 2.1 插入
    • 2.2 删除
  • 3 应用

介绍

最大堆和最小堆是二叉堆的两种形式。

  • 最大堆:根结点的键值是所有堆结点键值中最大者的堆。
  • 最小堆:根结点的键值是所有堆结点键值中最小者的堆。

而最大—最小堆集结了最大堆和最小堆的优点,这也是其名字的由来。

主要操作

不失一般性,只讨论根结点为最小层的情况。

插入

将节点插在二叉树的最后一个叶子结点位置,然后比较它与它父亲节点的大小:如果大则停止;如果小则交换位置,然后对父亲节点递归该过程直至根节点。复杂度为

一般来说,插入的位置可以不是最后一个叶子节点,可以作为任意中间节点的孩子节点插入,将这个叶子节点变为中间节点后,按上文所说的方法调整节点顺序以保证维持堆特性不变。

删除

要从堆中删除一个节点,用最后一个节点替换掉要删除的节点,然后调整节点顺序以维持堆特性。

应用

  • 双端优先队列
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/338671.html

上一篇:自由表
下一篇:复合类型
相关推荐