数据结构;最大堆;最小堆
发布时间
阅读量:
阅读量
定义:
最大堆与最小堆均为一种完全二叉树结构。
最大堆:其根节点所存储的关键字值为整个堆结构中的最大值,同时对于每一个具有子节点的节点而言,其关键字值均不小于其子节点的关键字值。
最小堆:其根节点所存储的关键字值为整个堆结构中的最小值,同时对于每一个具有子节点的节点而言,其关键字值均不大于其子节点的关键字值。
最大堆的插入操作
操作流程如下:
1 将待插入的新元素的编号 i 设定为当前堆中所有元素总数加 1,即 i = ++(*n),从而将新元素放置于最底层作为新的叶子节点。随后计算该节点的父节点位置 parent = i / 2;判断是否为初始空堆,并将新插入元素与父节点的关键字值进行比较;
2 若新插入元素的关键字值大于父节点的关键字值,即 item > heap[parent],则将父节点的内容向下移动,并将父节点设为当前处理对象,继续向上追溯其父节点位置,直至到达根节点;
3 最终将元素 item 插入至正确的位置;
最大堆的删除操作
在最大堆中进行删除操作时,通常是指移除其中的最大元素。具体步骤是先取出最后一个元素并将其置于根结点位置,随后执行删除操作,并对新的根结点进行调整以确保堆性质得以维持。
首先从结构中移除根结点,并将最后一个结点临时设置为新的根结点。接下来以该新根结点作为当前处理对象,并与它的两个子结点中关
全部评论 (0)
还没有任何评论哟~
