前言 - 为堆的学习做准备
二叉树的顺序存储
存储方式下标关系 堆 【heap】
概念 *** 作-向下调整
实战 - 将一组 记录完全二叉树数据 的 数组 转换成 大根堆。
向下调整 - 结论 问题
1、如何找到最后一棵子树2、如何将所有树的调整成大根堆 【遍历 每棵 树的 根结点,因为向下调整需要知道根结点的】每棵树的调整结束的位置,如何判定?如何构造一个 向下调整的函数 - 重点
附图 模拟实现 堆 - 程序框架
模拟实现 堆 的 时间复杂度 堆的应用 - 优先级队列
概念直接调用 优先级队列,系统默认生成是 小根堆。优先级队列 - 入队 和 出队 过程
大根堆情况 (向上调整)
模拟实现 堆 - offer 功能 - 入队模拟实现 堆 - poll 功能 - 出队
分析代码如下 模拟实现 堆 - peek 功能 - 返回队头元素 模拟实现 堆 【总程序】堆的其他应用-TopK 问题
思路一 :整体排序思路二 : 利用堆来实现 【这还不是Topk 问题,这里只是打底】思路二 :Topk思路
总结:在做实战题之前,我们需要先学习这篇文章[Java 对象 的 比较](https://blog.csdn.net/DarkAndGrey/article/details/122778354)
模拟topK问题【求一组数据的前k个最小值】,并解决它[实战题 - LeetCode - 373. 查找和最小的 K 对数字](https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/)题目分析解题 思维代码如下 堆排序
总结
实战 - 堆排序 本文结束
前言 - 为堆的学习做准备 二叉树的顺序存储前面所讲的二叉树,什么孩子表示法呀,还有 孩子双亲表示法啊,都是链式存储。
而现在讲的是:顺序存储一棵二叉树。
存储方式
使用数组保存二叉树结构,方式即将二叉树用层序遍历的方式放入数组中。
一般只适合表示完全二叉树,因为 非完全二叉树会有空间的浪费。【也就是说:如果使用顺序存储来存储一棵二叉树,那么,最好是完全二叉树,这样就不会有太多的空间被浪费】
这种方式的主要用法就是堆的表示。
下标关系
已知双亲(parent)的下标,则:
左孩子(left)下标 = 2 * parent + 1;
右孩子(right)下标 = 2 * parent + 2;
已知孩子(不区分左右)(child)下标,则:
双亲(parent)下标 = (child - 1)/ 2;
就是我在 二叉树那篇 文章 所讲的 二叉树的第五个性质
堆 【heap】 概念
1、堆在逻辑上是一棵完全二叉树
2、堆在物理上是保存在数组中。
3、满足任意节点的值 都大于 自身所在树中根结点的值,叫做小堆,或者小根堆,或者是最小堆。【每棵二叉树的根结点 都小于 左右孩子结点 - 小堆 / 小根堆 / 最小堆】
4. 满足任意节点的值 都小于 自身所在树中根结点的值,叫做大堆,或者大根堆,或者是最大堆。【每棵二叉树的根结点 都大于 左右孩子结点 -大堆 / 大根堆 / 最大堆】
5. 堆的基本作用是,快速找集合中的最值
无论是 大根堆还是小根堆, 它们的 最值【最大值 和 最小值】都处于 二叉树的 根结点处。要想获得 最值,直接 peek 方法,就能获得 树 的 根结点值 / 最值。
这也是为什么说: 堆 是 优先级队列。
所谓优先级队列:存入一个数据,是按照某种特殊规定来存储的。
而这种规则就是刚刚讲的 大小根堆的特性。将最值放在最容易获取的位置。
也就是说: 优先级队列 其 底层 是 一棵 完全二叉树 / 堆。
*** 作-向下调整
前提:左右子树必须已经是一个 堆 / 逻辑上是一棵完全二叉树。
实战 - 将一组 记录完全二叉树数据 的 数组 转换成 大根堆。
向下调整 - 结论
1. 调整是从最后一棵子树触发的
2、每棵子树的调整都是向下调整。
3、之所以称为向下调整,是因为 在 调整的过程中,根结点 是 跟 左右子树 进行交换,那么根结点是不是就下来了。所以才称为 向下调整【根结点的值,向下移动 / 与左右子树的值进行交换】。
问题 1、如何找到最后一棵子树
因为 堆 在 逻辑 上 是 一 棵 完全二叉树,物理上 其数据 是由数组保存的。
两者的共同点:完全二叉树的编号 与 数组下标 一致。
也就是说:我们只要获取数组的长度 len,那么 len -1 ,不就是 最后一棵子树的下标。
此时,我们是不是得到了一个 孩子结点 的 下标【child】?
根据 下标关系,我们就可以通过 孩子结点的下标,来获取 双亲节点 / 父 节点 的下标
parent == (child - 1)/ 2 》》parent == ((len - 1) - 1)/ 2
2、如何将所有树的调整成大根堆 【遍历 每棵 树的 根结点,因为向下调整需要知道根结点的】
很简单,既然我们通过 数组的长度,间接获取到了最后一棵子树的根结点【parent】,那么,我们直接 parent - - ,就可以获取所有子树,包括整棵树的根结点。
通过 双亲节点 parent 和 下标关系,我们就可以获取 其 左右子树的下标。
【 左子树:parent * 2 + 1;右子树:parent * 2 + 2】
每棵树的调整结束的位置,如何判定?
得出结论:其实每棵树的调整结束位置 都是一样的 :不能超过 数组长度。【细品】
如何构造一个 向下调整的函数 - 重点
// 向下调整 public void shiftDown(int parent,int len){ int child = parent * 2 + 1;// 左孩子 // 能进入该循环,说明 这个 parent 只少有一个孩子。 while(child < len){ // 获取 左右孩子的最大值 if(child+1 < len &&this.elements[child] < this.elements[child+1]){ child++; } // 判断 孩子最大值 是否 比 双亲节点 val 值 大 // 如果大,就需要进行交换 if(this.elements[child] > this.elements[parent]){ int tmp = elements[child]; elements[child] = elements[parent]; elements[parent] = tmp; // 见附图 parent = child; child = parent * 2 + 1; }else{ break; } } }
附图
模拟实现 堆 - 程序框架
import java.util.Arrays; public class Heap { public int[] elements;// 底层数组 public int usedSize;// 有效元素个数 // 构造方法 public Heap(int[] elements){ // 数组初始化容量 this.elements = new int[10]; } // 创建堆,获取 输入数组 的 数据 public void creationHeap(int[] array){ this.usedSize += array.length; if(isFull()){ this.elements = Arrays.copyOf(this.elements,this.elements.length*2); } this.elements = Arrays.copyOf(array,array.length); for(int parent = (this.usedSize -1 - 1)/2 ;parent >= 0;parent--){ // 向下调整 shiftDown(parent,this.usedSize); } } // 向下调整 public void shiftDown(int parent,int len){ int child = parent * 2 + 1;// 左孩子 // 能进入该循环,说明 这个 parent 只少有一个孩子。 while(child < len){ // 获取 左右孩子的最大值 if(child+1 < len &&this.elements[child] < this.elements[child+1]){ child++; } // 判断 孩子最大值 是否 比 双亲节点 val 值 大 // 如果大,就需要进行交换 if(this.elements[child] > this.elements[parent]){ int tmp = elements[child]; elements[child] = elements[parent]; elements[parent] = tmp; // 见附图 parent = child; child = parent * 2 + 1; }else{ break; } } } }
模拟实现 堆 的 时间复杂度
堆的应用 - 优先级队列 概念
在很多应用中,我们通常需要按照优先级情况 对待处理对象 进行处理,比如说首先处理优先级最高的对象,然后处理 次高的对象。
举个最简单的例子就是:
直接调用 优先级队列,系统默认生成是 小根堆。
下面我们就来实践。首先创建一个 优先级队列 / 堆。
按住 Ctrl ,左键点击框选部分,进入该类的内部。
按一下 alt + 7,就会d出功能菜单,如下图所示:【现在先关注队列的功能】
利用 offer 来给 优先级队列 / 堆 提供数据。再来通过 peek 方法 来观察 队头元素 / 堆的根结点,如果为 最小值,那么说 优先级队列默认是小根堆,反之,就是大根堆。
所谓优先级队列:不管是出队,还是入队。都得保证当前是大根堆 或者 小根堆。
优先级队列 - 入队 和 出队 过程 大根堆情况 (向上调整)
1、 首先按尾插方式放入数组
2、 比较其 和 其双亲的值 的 大小,如果双亲的值大,则满足堆的性质,插入结束
3、 否则,交换其和双亲位置的值,重新进行 2、3 步骤
4.、直到根结点
我们将其过程称为 向上调整。
向上调整:只需要一个参数【需要调整的 child 下标】
模拟实现 堆 - offer 功能 - 入队
// 入队 *** 作 public void offer(int val){ if(isFull()){ // 扩容 this.elements = Arrays.copyOf(this.elements,this.elements.length * 2); } elements[usedSize++] = val; //usedSize++; shiftUp(usedSize-1);// 有效元素个数 是 usedSize,最后一个元素的下标是 usedSize -1 } private void shiftUp(int child){ int parent = (child - 1)/2; while(child > 0){ if(this.elements[child] > this.elements[parent]){ int tmp = this.elements[child]; this.elements[child] = this.elements[parent]; this.elements[parent] = tmp; child = parent; parent = (child - 1) / 2; }else{ break; } } } public boolean isFull(){ return this.usedSize >= this.elements.length; }
模拟实现 堆 - poll 功能 - 出队 分析
代码如下
// 出队 *** 作 public int poll(){ if(isEmpty()){ throw new RuntimeException("优先级队列为空!"); } int tmp = this.elements[0]; this.elements[0] = this.elements[this.usedSize -1]; this.elements[this.usedSize - 1] = tmp; this.usedSize--; shiftDown(0,usedSize); return tmp; } // 判断队列 空不空 public boolean isEmpty(){ return this.usedSize == 0; }
模拟实现 堆 - peek 功能 - 返回队头元素
// 判断队列 空不空 public boolean isEmpty(){ return this.usedSize == 0; } public int peek(){ if(isEmpty()){ throw new RuntimeException("优先级队列为空!"); } return this.elements[0]; }
模拟实现 堆 【总程序】
import java.util.Arrays; public class Heap { public int[] elements;// 底层数组 public int usedSize;// 有效元素个数 // 构造方法 public Heap(){ // 数组初始化容量 this.elements = new int[10]; } // 创建堆,获取 输入数组 的 数据 public void creationHeap(int[] array){ this.usedSize += array.length; if(isFull()){ this.elements = Arrays.copyOf(this.elements,this.elements.length*2); } this.elements = Arrays.copyOf(array,array.length); for(int parent = (this.usedSize -1 - 1)/2 ;parent >= 0;parent--){ // 向下调整 shiftDown(parent,this.usedSize); } } // 向下调整 public void shiftDown(int parent,int len){ int child = parent * 2 + 1;// 左孩子 // 能进入该循环,说明 这个 parent 只少有一个孩子。 while(child < len){ // 获取 左右孩子的最大值 if(child+1 < len &&this.elements[child] < this.elements[child+1]){ child++; } // 判断 孩子最大值 是否 比 双亲节点 val 值 大 // 如果大,就需要进行交换 if(this.elements[child] > this.elements[parent]){ int tmp = elements[child]; elements[child] = elements[parent]; elements[parent] = tmp; // 见附图 parent = child; child = parent * 2 + 1; }else{ break; } } } // 入队 *** 作 public void offer(int val){ if(isFull()){ // 扩容 this.elements = Arrays.copyOf(this.elements,this.elements.length * 2); } elements[usedSize++] = val; //usedSize++; shiftUp(usedSize-1);// 有效元素个数 是 usedSize,最后一个元素的下标是 usedSize -1 } private void shiftUp(int child){ int parent = (child - 1)/2; while(child > 0){ if(this.elements[child] > this.elements[parent]){ int tmp = this.elements[child]; this.elements[child] = this.elements[parent]; this.elements[parent] = tmp; child = parent; parent = (child - 1) / 2; }else{ break; } } } // 判断队列满没满 public boolean isFull(){ return this.usedSize >= this.elements.length; } // 出队 *** 作 public int poll(){ if(isEmpty()){ throw new RuntimeException("优先级队列为空!"); } int tmp = this.elements[0]; this.elements[0] = this.elements[this.usedSize -1]; this.elements[this.usedSize - 1] = tmp; this.usedSize--; shiftDown(0,usedSize); return tmp; } // 判断队列 空不空 public boolean isEmpty(){ return this.usedSize == 0; } public int peek(){ if(isEmpty()){ throw new RuntimeException("优先级队列为空!"); } return this.elements[0]; } }
堆的其他应用-TopK 问题
给我们一百万个数据,让你找到前10个最大的元素。
目前来说:我们知道堆排序时间复杂度 最快: log2 N * N;最慢: N
思路一 :整体排序
对整体进行排序,输出前10个最大的元素。
对整体排序这不是一个非常好的思路!
99%的人都能想出来:直接对底层数组进行排序,输出前10个最大的元素。
这样做,出这题的意义就不大。
思路二 : 利用堆来实现 【这还不是Topk 问题,这里只是打底】
用堆来解决。
思路:将数据建成大根堆。
假设,建好的大根堆如下图所示:
假设,我们要在这个堆上找到 前三个 最大值,该怎么做?
思路二 :Topk思路
还是跟思路二一样,去求一组数据的前三个最大值。
总结:
1、如果求前K个最大的元素,要建一个小根堆。
2、如果求 前K个最小的元素,要建一个大根堆。
3、如果是求第k大的元素,建一个小堆,小根堆 堆顶的元素就是第k大的元素。
4、如果是求第k小的元素,建一个大堆,大根堆 堆顶的元素就是第k小的元素。
在做实战题之前,我们需要先学习这篇文章Java 对象 的 比较
模拟topK问题【求一组数据的前k个最小值】,并解决它
import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; public class TopK { public static int[] topK(int[] array,int k){ // 创建一个大小为 k 的 大根堆 PriorityQueuemaxHeap = new PriorityQueue<>(k, new Comparator () { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }); for(int i = 0;i array[i]){ maxHeap.poll();// 先将堆顶元素d出,优先级队列会自行调整一下 maxHeap.offer(array[i]);// 后面入队也是一样,也会自行调整一下 } } } // 此时 maxHeap 堆里,存储的是 前 k 个最小的 值 // 现在要做的是 将其 转换称是数组,返回 int[] tmp = new int[k]; for(int i = 0;i < k;i++){ tmp[i] = maxHeap.poll(); } return tmp; } public static void main(String[] args) { int[] array = {18,21,8,10,34,12}; int[] tmp =topK(array,3);// 求前三个最小值 System.out.println(Arrays.toString(tmp)); } }
实战题 - LeetCode - 373. 查找和最小的 K 对数字
题目分析
给了我们两个升序(元素顺序:从小到大)数组 num1 和 num2,让我们分别从 num1 和 num2 中,各自选取 一个 数据,让其 组成 k 个 两个数之和最小 的 组合。
选取的数可以重复利用。
解题 思维
代码如下
class Solution { public List> kSmallestPairs(int[] nums1, int[] nums2, int k) { // 创建 一个大小为 k 的 大根堆 PriorityQueue
> maxHeap = new PriorityQueue<>(k,new Comparator
>(){ @Override public int compare(List
o1,List o2){ return ((o2.get(0) + o2.get(1)) - (o1.get(0) + o1.get(1))); } }); // 我们不需要将数组 num1 和 num2 遍历完 // 因为 这两个数组是升序,前k个最小数对,一定是 有 num1 和 num2 前k 个元素 组成的。 for(int i = 0;i < Math.min(nums1.length,k);i++){ for(int j = 0;j < Math.min(nums2.length,k);j++){ // 先放入 k 个 数对 if(maxHeap.size()< k){ List tmpList = new ArrayList<>(); tmpList.add(nums1[i]); tmpList.add(nums2[j]); maxHeap.offer(tmpList); }else{// 从 k +1 个 数对,开始判断 int top = maxHeap.peek().get(0) +maxHeap.peek().get(1); if(top >(nums1[i] + nums2[j])){ // d出 maxHeap.poll(); List tmpList = new ArrayList<>(); tmpList.add(nums1[i]); tmpList.add(nums2[j]); // 入队 maxHeap.offer(tmpList); } } } } // 为返回值做准备 List > result = new ArrayList<>(); // 循环判断条件,需要加上 一个判断 堆是不是为空 // 根据示例三:两个数组元素 可能存在 不足以构成 k 个最小数对 的情况 for(int i = 0; i < k && !maxHeap.isEmpty();i++ ){ result.add(maxHeap.poll()); } return result; } }
堆排序
总结
1、将数据调整为 大根堆、
2、0 下标 与 最后一个未排序的元素进行交换即可。
3、循环上述两个 *** 作,直至 最后一个未排序的元素 下标为 0.。
实战 - 堆排序
public void heapTraversal(){ // 最后一个未排序元素的下标 int last = this.elements.length - 1; while(last > 0){ int tmp = this.elements[0]; this.elements[0] = this.elements[last]; this.elements[last] = tmp; shiftDown(0,last); last--; } } // 向下调整 public void shiftDown(int parent,int len){ int child = parent * 2 + 1;// 左孩子 // 能进入该循环,说明 这个 parent 只少有一个孩子。 while(child < len){ // 获取 左右孩子的最大值 if(child+1 < len &&this.elements[child] < this.elements[child+1]){ child++; } // 判断 孩子最大值 是否 比 双亲节点 val 值 大 // 如果大,就需要进行交换 if(this.elements[child] > this.elements[parent]){ int tmp = elements[child]; elements[child] = elements[parent]; elements[parent] = tmp; // 见附图 parent = child; child = parent * 2 + 1; }else{ break; } } }本文结束
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)