【算法与数据结构专场】二叉堆是什么鬼？ (2)

接着，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算法优化的那篇，会在之后给出。

获取更多原创文章，可以关注下我的公众号：苦逼的码农，我会不定期分享一些资源和软件等。后台回复礼包送你一份时下热门的资源大礼包，同时也感谢把文章介绍给更多需要的人