大小堆及常用堆算法
大小堆
概念上
-
大顶堆:父节点的值大于等于子节点的值
-
小顶堆:父节点的值小于等于子节点的值
结构上
- 都是完全二叉树结构
- 获取最值都是O(1),插入删除都是O(log(n))
使用场景
- 大顶堆:用于快速获取最大值的场景.比如堆排序的升序排序
- 小顶堆:比如优先级队列处理优先级高(权值小)的任务
常用算法
维护堆结构涉及两个个主要方法
- heapify() 建堆,用于堆结构的初始化,采用弗洛伊德算法,从最后一个非叶子节点开始,向前遍历做down
- down() 下潜节点,新增/删除节点后维护堆结构,和左右孩子比较,找到大的做交换,然后递归下潜(大顶堆)
public static void heapify(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {//最后一个非叶子节点索引为 len*2-1
down(arr, i);
}
}
public static void down(int[] arr, int parent) {
//1.求出左右孩子索引值
int lef = 2 * parent + 1;
int rig = lef + 1;
//2.比较出最大值
int max = parent;
if (lef < arr.length && arr[lef] > arr[max]) {
max = lef;
}
if (rig < arr.length && arr[rig] > arr[max]) {
max = rig;
}
//3.交换,递归下潜
if (max!=parent){
swap(arr,parent,max);
down(arr,max);//注意递归位置是满足交换后,此句作为递归的终止条件
}
}
public static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
fengdongnan的博客 文章被收录于专栏
记录fengdongnan的知识产出文档,欢迎大家来一起交流学习
