面试官: 今天我们不谈二叉树, 谈谈你对二叉堆的理解?
面试官: 二叉树都耳熟能详了,谈谈你对二叉堆的理解?
o_O||: 堆我听过,冒昧问句,二叉堆是啥?
面试官: 打扰了!下一位...
啥是堆?
堆,英文名叫heap.
堆的定义
堆是一类特殊数据结构的统称,通常是一个可以被看作一棵树的数组对象.
堆的特性
堆是一个完全二叉树
堆中的任意一个节点值大于等于或小于等于子树的任意节点
堆的分类
最大堆
最大堆的任何一个父节点的值,都大于等于它的左右子节点的值.
最小堆
最小堆的任何一个父节点的值,都小于等于它的左右子节点的值.
上面提到堆是一个完全二叉树,什么是完全二叉树?
提到完全二叉树,看一下两类特殊的二叉树:
然后看一下绕口的定义:
完全二叉树：设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边 满二叉树：深度为k且有2^k-1个结点的二叉树称为满二叉树
使用完全二叉树的原因是易于存储，并且便于索引。那问题来了,堆这种数据结构存在的原因是什么。它作为一个工具，让什么样的问题变得简单了?
如果仅仅是需要得到一个有序的序列，使用排序就可以很快完成，并不需要去组织一个新的数据结构。但是如果我们的需求是对于一个随时会有更新的序列，我要随时知道这个序列的最小值或最大值是什么。显然如果是线性结构，每次插入之后，假设原数组是有序的，那使用二分把它放在正确的位置也未尝不可，但是插入的时候从数组中留出空位就需要O(n)的时间复杂度，删除的时候亦然。
可是如果我们将序列看作是一个集合，我们需要的是这个集合的一个最小值，并且，在它被任意划分成为若干个子集的时候，这些子集的最小值我们也是知道的，这些子集被不断划分，我们依然知道这些再次被划分出来的子集的最小值。而且我们去想办法去保持这样的一个性质，那么这个问题是不是变得非常好解决了呢？那么问题就转换成了一种集合之间的关系，并且是非常明显的一种包含关系，那么最适合于解决这种集合上的关系的数据结构是什么呢？那么就是树，所以就形成了这样的一种树，他的每一个节点都比它的子节点们小或者大。
当我们插入一个新的节点的时候，实际上我们需要去调整的大部分时候只是这棵树上的一条路径，也就是决定它在哪一个集合里面，树上的路径长度相对于这个集合，由于是对数级别的，所以非常可以接受，那么这种数据结构也就应运而生，而这个数据结构为什么叫做堆，那就不知道了。
啥是二叉堆?
二叉堆是一种特殊的堆…
二叉堆的根节点叫做堆顶,最大堆和最小堆的特点决定了:
最大堆的堆顶一定是整个堆中的最大元素,
最小堆的堆顶一定是整个堆中的最小元素.
二叉堆有哪些骚操作?
二叉堆有如下操作:
1.插入节点(insert)
2.删除节点(remove)
3.构建二叉堆(buildHeap)
举例说明
一. 插入节点的操作:
当二叉堆插入节点时,插入位置是完全二叉树的最后一个位置,假设插入一个值为0的节点:
动图说明一下插入节点的过程:
新节点0的父节点比它大,不符合最小堆的特性,于是让0上浮,和父节点交换位置
继续用新节点0和父节点2进行比较,0小于2,新节点继续上浮
继续比较,最终新节点0上浮到了堆顶的位置
二. 删除节点的过程:
还是以上面原始二叉堆举例,删除堆顶节点1:
动图说明一下删除节点的过程:
为了继续维持完全二叉树的结构,把堆的最后一个节点9临时补到原本堆顶的位置
然后让暂处堆顶位置的节点9和它的左右子节点进行比较,左右子节点中最小的一个比它小(子节点2和3,节点2是其中最小的子节点),让节点9下沉,即:2和9交换位置
继续让节点9和它的左右子节点比较,左右子节点中最小的是4,9比4大,则让节点9下沉,即:4和9交换位置
继续,只剩左子节点8,9比8大,让节点9下沉,即:8和9交换位置
最终调整后的堆为:
三. 构建二叉堆的过程
构建二叉堆就是把一个无序的完全二叉树调整为二叉堆,本质就是让所有非叶子节点依次下沉.
从最后一个非叶子节点开始:
如果该节点大于左右子节点中最小的一个,则该节点下沉
依次向上,将所有非叶子节点均与其子节点比较
通过若干轮的比较和下沉操作,最终每一个节点都小于它的左右子节点,一个无序的完全二叉树就被构建成了一个最小堆
二叉堆的代码实现
需要说明的是,二叉堆虽然是一个完全二叉树,但是它的存储方式并不是链式存储,而是顺序存储,换句话说,二叉堆的所有节点都存储在数组中.
问题来了,在数组中,没有左右指针的情况下,如何定位一个父节点的左右子节点?
没错,就是下标!
假设父节点的下标是parent, 那么:
它的左子节点的下标就是2*parent+1
右子节点下标就是2*parent+2
代码实现如下:
package com.xgcd.lab.sort;
import java.util.Arrays;
/**
* @description: 二叉堆
* 二叉堆是堆排序和优先队列的基础.
* 二叉堆虽然是一个完全二叉树,但它的存储方式并不是链式存储,而是顺序存储.换句话说,二叉堆的所有节点都存储在数组中.
* 在数组中,在没有左右指针的情况下,如何定位一个父节点的左右子节点?
* 可以依靠数组下标来计算:假设父节点下标是parent,那它的左子节点下标就是2*parent+1,右子节点下标就是2*parent+2
* @author: liangyadong
* @date: 2021/7/20 0:07
*/
public class BinaryHeap {
/**
* "上浮"调整
*
* @param arr 待调整的堆
*/
public static void upAdjust(int[] arr) {
int childIndex = arr.length - 1;
int parentIndex = (childIndex - 1) / 2;
// temp保存插入的叶子节点的值,用于最后的赋值
int temp = arr[childIndex];
while (childIndex > 0 && temp < arr[parentIndex]) {
// 无需真正交换,单向赋值即可
arr[childIndex] = arr[parentIndex];
childIndex = parentIndex;
parentIndex = (parentIndex - 1) / 2;
}
arr[childIndex] = temp;
}
/**
* "下沉"调整
*
* @param arr 待调整的堆
* @param parentIndex 要"下沉"的父节点
* @param length 堆的有效大小
*/
public static void downAdjust(int[] arr, int parentIndex, int length) {
// temp保存父节点的值,用于最后的赋值
int temp = arr[parentIndex];
int childIndex = 2 * parentIndex + 1;
while (childIndex < length) {
// 如果有有节点,并且右节点小于左节点的值,则定位到右节点
if (childIndex + 1 < length && arr[childIndex + 1] < arr[childIndex]) {
childIndex++;
}
// 如果父节点小于任何一个子节点的值,则直接跳出
if (temp <= arr[childIndex]) {
break;
}
// 无须真正交换,单向赋值即可
arr[parentIndex] = arr[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
arr[parentIndex] = temp;
}
/**
* 构建堆
*
* @param arr 待调整的堆
*/
public static void buildHeap(int[] arr) {
// 从最后一个非叶子节点开始,依次做"下沉"调整
for (int i = (arr.length - 2) / 2; i >= 0; i--) {
downAdjust(arr, i, arr.length);
}
}
public static void main(String[] args) {
int[] arr = {1, 4, 3, 5, 7, 9, 8, 6, 0, 10};
upAdjust(arr);
System.out.println(Arrays.toString(arr));
arr = new int[]{2, 3, 4, 1, 6, 9, 8, 7, 10, 0};
buildHeap(arr);
System.out.println(Arrays.toString(arr));
}
}
本篇完.
习惯沉淀
一线码农的学习见闻与思考
Official Account