堆的常用方法
1.构建优先队列
2.堆排
堆的分类
1.最大堆 : 父节点总比子节点大, 同级结点无顺序要求
2.最小堆 : 父节点总比子节点大, 同级结点无顺序要求
例子
上面就是一个简单的最大堆
堆的特点
1.顺序结构
有最大堆和最小堆之分,不在复述
2.储存结构
堆与二叉树储存方式不太一样
由于二叉树用顺序链表构建,我们常见有二叉树:
但堆是用数组构建 , 所以, 上图所示堆中是不可能出现的。
在堆中,在当前层级都已填满前是不予许展开下一层的,在做节点出现前是不会先出现右结点的。
注意:由于堆由数组实现,不存在指针,也不需要为指针分配空间,所以堆在空间效率上是优于普通树的
堆的实现
比如我们要将序列 : 【5 2 7 10 1】存入最大堆中,每次将元素插入堆的末端
-
插入5 :【5】
-
插入2 :【5,2】 //此时2为5 的左儿子
-
插入7 :【5,2,7】 // 此时7为5的右儿子,由于7 大于5需要将7和5交换位置
-
调整 : 【7,2,5】 //此时7为根节点,5为7的右儿子
-
插入10 :【7,2,5,10】//此时10为2的左儿子
-
调整 : 【7,10,5,2】
-
调整 : 【10,7,5,2】
-
插入1:【10,7,5,2,1】
注意 :节点在数组中的下标 和它的父节点的下标之间有一个映射关系。
一个结点的下标为 i则他的儿子,父亲下标应为
parent(i) = floor((i - 1)/2)
left(i) = 2i + 1
right(i) = 2i + 2
`
下标 | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
元素 | 10 | 7 | 5 | 2 | 1 |
注意:根节点10没有父节点
举个栗子
数组 : 【10,14,25,33,81,82,99】
上面的数组就是一个有效的最小堆
注意:并不是每一个最小堆都是一个有序数组!要将堆转换成有序数组,需要使用堆排序
有关操作
基础操作
shiftUp()
:将当前结点与父节点交换位置
shiftDown()
:将当前结点与最大(最大堆),最小(最小堆)子节点交换位置
注意:shiftUp 或者 shiftDown 是一个递归的过程,所以它的时间复杂度是 O(log n)**
其他操作
insert(value)
: 在堆的尾部添加一个新的元素,然后使用 shiftUp
来修复对。
remove()
: 移除并返回最大值(最大堆)或者最小值(最小堆)。为了将这个节点删除后的空位填补上,需要将最后一个元素移到根节点的位置,然后使用 shiftDown
方法来修复堆。
removeAtIndex(index)
: 和 remove()
一样,差别在于可以移除堆中任意节点,而不仅仅是根节点。当它与子节点比较位置不时无序时使用 shiftDown()
,如果与父节点比较发现无序则使用 shiftUp()
。
replace(index, value)
:将一个更小的值(最小堆)或者更大的值(最大堆)赋值给一个节点。由于这个操作破坏了堆属性,所以需要使用 shiftUp()
来修复堆属性。
插入
一个堆的数组:【10,7,5,2,1】,现在需要插入一个数12
1.插入12:【10,7,5,2,1,12】
2.shiftUp
调整:【12,7,10,2,1,5】
删除
堆数组:【12,7,10,2,1,5】,删除12;
1.删除后尾结点交换到该位置:【5,7,10,2,1】
2.shiftDown
调整:【10,7,5,2,1】