二叉堆的构建以及添加/删除实现
2019-07-17 本文已影响0人
just_like_you
二叉堆的学习记录，实现的过程以及源码
每个根节点都大于或等于子节点的完全二叉树称为大顶锥，每个根节点都小于或等于子节点的完全二叉树称为小顶锥，大顶锥的锥顶就是整个树的最大值，小顶锥则是最小值，由于是完全二叉树，所以底层使用的物理数据结构为数组实现。
- 从末尾添加，二叉堆要使用
上浮操作来完成自调节 - 从锥顶删除，将最末尾元素替换锥顶，然后开始
下沉操作完成自调节 - 构建二叉锥，则是使用从最大的非子叶节点依次
下沉完成自调节
上浮 ： 将元素与其父节点比较，若小于，则保存替换。到索引值小于0或者大于等于父节点的时候停止，再使用保存的值替换当前子节点即可。其中，获取父节点的索引和子节点的关系
int parentIndex = (childIndex-1)/2
下沉 ： 将元素与左右子节点中较小的进行比较，若大于，则保存替换，到索引值大于树长度-1或者不大于较小节点结束，然后替换父节点即可。其中父节点和子节点的关系是：
int childIndex = 2 * parentIndex + 1;
构建heap的非子叶节点的最大索引值和树的长度关系为：
int maxIndex = (arr.length -2 )/2;
源码如下
/**
* @author hj
* 2019-07-17 22:44
* 关于二叉堆的测试类
*/
public class BinaryTreeHeapTest {
public static void main(String[] args) {
int[] arr = {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
upAdjust(arr);
System.out.println(Arrays.toString(arr));
int[] arr1 = {0, 1, 2, 3, 5, 6, 7, 8, 9, 10};
buildHeap(arr);
System.out.println(Arrays.toString(arr1));
}
/**
* 上浮调整
*
* @param arr 二叉堆
*/
public static void upAdjust(int[] arr) {
int lastIndex = arr.length - 1;
int parentIndex = (lastIndex - 1) / 2;
int tmp = arr[lastIndex];
while (arr[parentIndex] > tmp && lastIndex > 0) {
//这里只是单纯的赋值即可，在最后上浮结束完成交换
arr[lastIndex] = arr[parentIndex];
//获取下一轮的索引
lastIndex = parentIndex;
parentIndex = (parentIndex - 1) / 2;
}
arr[lastIndex] = tmp;
}
/**
* 下沉调整
*
* @param arr 要调整的堆
* @param parentIndex 下沉的父节点的索引
*/
public static void downAdjust(int[] arr, int parentIndex) {
int length = arr.length;
int tmp = arr[parentIndex];
int childIndex = 2 * parentIndex + 1;
while (childIndex < length) {
//获取左右节点中最小值索引
if (childIndex + 1 < length && arr[childIndex + 1] < arr[childIndex]) {
childIndex++;
}
//小于左右节点中最小值则退出
if (tmp <= arr[childIndex]) {
break;
}
arr[parentIndex] = arr[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
//下沉结束
arr[parentIndex] = tmp;
}
/**
* 构建二叉堆
*
* @param arr 带构建的二叉树
*/
public static void buildHeap(int[] arr) {
for (int i = (arr.length - 2) / 2; i >= 0; i--) {
downAdjust(arr, i);
}
}
}
