二叉堆是一种应用很广的数据结构, 今天, 我们就来简单讲讲二叉堆.
[算法与数据结构专场] BitMap 算法基本操作代码实现 https://mp.weixin.qq.com/s/-gZWjKqOTRby22Xh4XikVw
[算法与数据结构专场] BitMap 算法介绍 https://mp.weixin.qq.com/s/nls2DTlnhItusuSSJEz8Vg
什么是二叉堆?
二叉堆是一种特殊的堆. 具有如下的特性:
具有完全二叉树的特性.
堆中的任何一个父节点的值都大于等于它左右孩子节点的值, 或者都小于等于它左右孩子节点的值.
根据第二条特性, 我们又可以把二叉堆分成两类:
1, 最大堆: 父节点的值大于等于左右孩子节点的值.
2, 最小堆: 父节点的值小于等于左右孩子节点的值.
我们把二叉堆的根节点称之为堆顶. 根据二叉堆的特性, 堆顶要嘛是整个堆中的最大元素, 要嘛是最小元素.
今天, 我们主要来讲讲二叉堆的三个主要操作:
插入一个节点.
删除一个节点.
构建一个二叉堆.
不过这里需要注意的是, 在二叉堆这种结构中, 对于删除一个节点, 我们一般删的是根节点.
下面我们以最小堆为例子, 来讲讲这些操作.
插入一个节点.
刚才我们说二叉堆具有完全二叉树的特性, 因此, 我们在插入一个节点的时候, 应该先保证节点插入后, 它仍然是一颗完全二叉树, 然后再来进行调整, 使它满足二叉堆的另一个特性.
所以, 在插入的时候, 我们把新节点插到完全二叉树的最后一个位置. 例如:
插入 0.
之后我们再来进行调整, 调整的原则是: 让新插入的节点与它的父节点进行比较, 如果新节点小于父节点, 则让新节点上浮, 即和父节点交换位置.
上浮之后继续和它的父节点进行比较, 直到父节点的值小于或等于该节点, 才停止上浮, 即插入结束. 例如:
0 比 5 小, 上浮.
0 比 2 小于, 上浮.
0 比 1 小, 上浮.
已经到达堆顶了, 插入结束.
删除节点.
前面说了, 删除节点一般删除的是根节点.
和插入一样, 由于二叉堆具有完全二叉树的特性, 因为删除时候, 首先我们是要马上恢复它具有完全二叉树的特性, 所以我们是采取这样的策略: 把根节点删除之后, 用二叉堆的最后一个元素顶替上来, 然后在进行调整恢复. 例如:
把 0 删除了之后, 5 替换上来.
之后再来调整, 调整的规则和插入差不多类似, 采取下沉的策略: 让 5 和左右孩子节点相比较, 如果左右节点有小于 5 的, 则让那个较小的孩子代替 5 的位置, 然后 5 下沉.
下沉之后, 5 继续和左右孩子相比, 直到左右孩子都大于或等于 5 才结束.
如: 5 比 1,3 都大, 1 代替 5 的位置
5 比 4,2 都大, 2 代替 5 的位置.
5 已经不在具有左右孩子了, 删除结束.
构建二叉堆
所谓构建, 就是给你一个有 n 个节点的无序的完全二叉树, 然后把它构建成二叉堆.
刚才我们在删除一个节点的时候, 把最后一个元素补到根元素的位置上去, 然后再让这个元素依次下沉, 实际上, 在这个元素还没有下沉之前, 它就可以看作是一颗无序的完全二叉树了.
也就是说, 要把一个无序的完全二叉树调整为二叉堆, 我们可以让所有非叶子节点依次下沉. 不过下沉的顺序不是从根节点开始下沉 (想一下相必你就 知道不能从根节点开始下沉), 而是从下面的非叶子节点下称, 在依次往上. 举个例子:
对于这样一颗无序的完全二叉树
8 进行下沉.
接着, 5 进行下沉.
2 没问题, 之后让 7 进行下沉
调整完成, 构建结束.
代码实现
不过这里需要说明的是, 我们二叉树一般是采用链表的方式来实现的, 但二叉堆我们是采用数组的方式来存储的.
如果知道了一个节点的位置, 如何知道一个节点的左右孩子节点的位置呢?
这其实不难, 根据完全二叉树的特点, 假如一个节点的下标为 n, 则可以求得它左孩子的下标为: 2 n+1; 右孩子下标为: 2 n+2.
下面是构建代码的实现:
- public class BinaryHeap {
- // 上浮操作, 对插入的节点进行上浮
- /**
- *
- * @param arr
- * @param length : 表示二叉堆的长度
- */
- public static int[] upAdjust(int arr[], int length){
- // 标记插入的节点
- int child = length - 1;
- // 其父亲节点
- int parent = (child - 1)/2;
- // 把插入的节点临时保存起来
- int temp = arr[child];
- // 进行上浮
- while (child> 0 && temp <arr[parent]) {
- // 其实不用进行每次都进行交换, 单向赋值就可以了
- // 当 temp 找到正确的位置之后, 我们再把 temp 的值赋给这个节点
- arr[child] = arr[parent];
- child = parent;
- parent = (child - 1) / 2;
- }
- // 退出循环代表找到正确的位置
- arr[child] = temp;
- return arr;
- }
- /**
- */
- /**
- * 下沉操作, 执行删除操作相当于把最后
- * * 一个元素赋给根元素之后, 然后对根元素执行下沉操作
- * @param arr
- * @param parent 要下沉元素的下标
- * @param length 数组长度
- */
- public static int[] downAdjust(int[] arr, int parent, int length) {
- // 临时保证要下沉的元素
- int temp = arr[parent];
- // 定位左孩子节点位置
- int child = 2 * parent + 1;
- // 开始下沉
- while (child < length) {
- // 如果右孩子节点比左孩子小, 则定位到右孩子
- if (child + 1 < length && arr[child]> arr[child + 1]) {
- child++;
- }
- // 如果父节点比孩子节点小或等于, 则下沉结束
- if (temp <= arr[child])
- break;
- // 单向赋值
- arr[parent] = arr[child];
- parent = child;
- child = 2 * parent + 1;
- }
- arr[parent] = temp;
- return arr;
- }
- /**
- * 构建操作
- *
- * @param arr
- */
- public static int[] buildHead(int[] arr,int length) {
- // 从最后一个非叶子节点开始下沉
- for (int i = (length - 2) / 2; i>= 0; i--) {
- arr = downAdjust(arr, i, length);
- }
- return arr;
- }
- }
本次讲解到此结束. 下篇继续讲解和堆有关的知识点. 至于 bitmap 算法优化的那篇, 会在之后给出.
获取更多原创文章, 可以关注下我的公众号: 苦逼的码农, 我会不定期分享一些资源和软件等. 后台回复礼包送你一份时下热门的资源大礼包, 同时也感谢把文章介绍给更多需要的人
来源: https://www.cnblogs.com/kubidemanong/p/9711705.html