JAVA数据结构 DAY8-堆

本系列可作为JAVA学习系列的笔记文中提到的一些练习的代码小编会将代码复制下来大家复制下来就可以练习了方便大家学习。点赞关注不迷路您的点赞、关注和收藏是对小编最大的支持和鼓励系列文章目录JAVA初阶---------已更完JAVA数据结构 DAY1-集合和时空复杂度JAVA数据结构 DAY2-包装类和泛型JAVA数据结构 DAY3-List接口JAVA数据结构 DAY4-ArrayListJAVA数据结构 DAY5-LinkedListJAVA数据结构 DAY6-栈和队列JAVA数据结构 DAY7-二叉树JAVA数据结构 DAY8-堆JAVA数据结构 DAY9 equals、Comparable、Comparator 与 PriorityQueue 深度解析JAVA数据结构 DAY10-排序拓展目录手把手教你用 ArrayList 实现杨辉三角从逻辑推导到每行代码详解链表高频 6 题精讲 | 从入门到熟练掌握链表操作二叉树高频题精讲 | 从入门到熟练掌握二叉树操作二叉树高频题精讲 | 从入门到熟练掌握二叉树操作2目录目录系列文章目录拓展目录目录前言一、优先级队列打破普通队列 FIFO 规则的高级队列1.1 普通队列的局限1.2 优先级队列的定义二、堆Heap完全二叉树的特殊顺序存储结构2.1 堆的官方定义2.2 堆的两种形态2.3 堆的两大核心性质2.4 堆的顺序存储规则下标公式三、堆的核心操作向下调整、向上调整、建堆、插入、删除3.1 堆的向下调整以小堆为例适用前提调整步骤小堆完整代码实现时间复杂度3.2 堆的创建任意数组转堆建堆步骤建堆代码3.3 建堆时间复杂度详细推导面试常问3.4 堆的插入操作插入步骤向上调整代码小堆3.5 堆的删除操作删除步骤四、手动模拟实现优先级队列MyPriorityQueue五、Java 官方 PriorityQueue 完整使用指南5.1 PriorityQueue 核心特性必背5.2 常用构造方法5.3 常用核心 API5.4 如何创建大根堆面试高频5.5 JDK 1.8 扩容机制源码级六、堆的三大经典应用6.1 堆排序6.2 Top-K 问题面试 / 笔试最高频七、配套习题 详细答案习题 1习题 2习题 3习题 4八、全文总结最强思维导图版总结前言小编作为新晋码农一枚会定期整理一些写的比较好的代码作为自己的学习笔记会试着做一下批注和补充如转载或者参考他人文献会标明出处非商用如有侵权会删改欢迎大家斧正和讨论在数据结构与算法体系中优先级队列是解决 “按优先级而非先后顺序出队” 场景的核心结构而它的底层基石就是堆。无论是面试高频考点、算法题Top-K、堆排序还是工程中的任务调度、事件优先级处理堆与优先级队列都是必须吃透的核心知识点。本文将完整覆盖文档全部内容从概念到原理、从手动实现到 Java API、从习题到应用用最细致的讲解帮你彻底掌握。一、优先级队列打破普通队列 FIFO 规则的高级队列1.1 普通队列的局限我们之前学过的普通队列Queue遵循严格的先进先出FIFO规则先入队的元素一定先出队。但现实中大量场景不适合 FIFO手机正在玩游戏突然来电 → 来电必须优先处理班级排座位 → 成绩更优的学生优先选座操作系统任务调度 → 高优先级任务先执行医院急诊 → 危重病人优先就诊这些场景的核心需求出队时优先级最高的元素先出普通队列无法满足。1.2 优先级队列的定义优先级队列Priority Queue是一种特殊的队列它不遵守先进先出而是每次出队都取出当前优先级最高的元素每次入队都能维持内部的优先级规则它只需要提供两个最核心操作添加新元素获取 / 删除最高优先级元素在JDK 1.8中Java 集合框架的PriorityQueue底层完全基于堆Heap实现堆是优先级队列的底层数据结构。二、堆Heap完全二叉树的特殊顺序存储结构2.1 堆的官方定义假设有一个关键码集合K {k0, k1, k2, …, kn-1}把它按完全二叉树的层序规则存储在一维数组中并且满足小堆Ki ≤ K[2i1] 且 Ki ≤ K[2i2]大堆Ki ≥ K[2i1] 且 Ki ≥ K[2i2]满足以上条件的结构就称为堆。2.2 堆的两种形态大根堆最大堆堆顶元素是整个堆的最大值任意父节点 ≥ 子节点小根堆最小堆堆顶元素是整个堆的最小值任意父节点 ≤ 子节点2.3 堆的两大核心性质堆一定是一棵完全二叉树只有完全二叉树才能用数组高效存储不会浪费大量空间。堆中任意节点的值永远不大于 / 不小于它的孩子节点这是堆的 “有序性”也是优先级队列能快速取最值的原因。2.4 堆的顺序存储规则下标公式堆用数组存储通过下标可以O (1) 找到父节点、左孩子、右孩子设当前节点下标为i父节点下标(i - 1) / 2左孩子下标2 * i 1右孩子下标2 * i 2注意非完全二叉树不适合顺序存储因为要存大量空节点空间利用率极低。三、堆的核心操作向下调整、向上调整、建堆、插入、删除堆的所有功能都基于两个最基础的算法向下调整、向上调整。3.1 堆的向下调整以小堆为例适用前提以某节点为根的左子树、右子树已经是堆只有根节点不满足堆性质需要向下调整。调整步骤小堆用parent标记需要调整的节点child先标记左孩子完全二叉树一定先有左孩子如果右孩子存在找出左右孩子中更小的那个用child标记它比较parent和child如果parent ≤ child已经满足堆性质结束调整如果parent child交换两者继续向下调整循环直到child超出数组范围到叶子节点完整代码实现/** * 小堆的向下调整 * param array 存储堆的数组 * param parent 要调整的父节点下标 */ public void shiftDown(int[] array, int parent) { // 先指向左孩子 int child 2 * parent 1; int size array.length; // 孩子存在才循环 while (child size) { // 右孩子存在且更小child 切换到右孩子 if (child 1 size array[child 1] array[child]) { child child 1; } // 父节点更小满足堆直接退出 if (array[parent] array[child]) { break; } // 不满足交换父节点与较小孩子 int temp array[parent]; array[parent] array[child]; array[child] temp; // 继续向下调整 parent child; child 2 * parent 1; } }时间复杂度最坏情况从根走到叶子次数 完全二叉树高度时间复杂度O (log₂n)3.2 堆的创建任意数组转堆如果数组是完全无序的左右子树都不是堆不能直接调整根节点必须从底部往上批量调整。建堆步骤找到倒数第一个非叶子节点下标公式(array.length - 2) / 2或(array.length - 2) 1从这个节点开始向前遍历到根节点下标 0每个节点都执行一次向下调整建堆代码/** * 将普通数组调整为堆 */ public static void createHeap(int[] array) { // 找到倒数第一个非叶子节点 int lastParent (array.length - 2) 1; // 从后往前逐个向下调整 for (int root lastParent; root 0; root--) { shiftDown(array, root); } }3.3 建堆时间复杂度详细推导面试常问我们用满二叉树近似计算满二叉树是特殊的完全二叉树设树高度为 h总结点数 n ≈ 2ʰ - 1总调整步数T(n) 2⁰·(h-1) 2¹·(h-2) 2²·(h-3) … 2ʰ⁻²·1使用错位相减法2·T(n) 2¹·(h-1) 2²·(h-2) … 2ʰ⁻¹·1两式相减后化简T(n) 2ʰ - 1 - h ≈ n最终结论建堆的时间复杂度O (N)3.4 堆的插入操作堆的插入必须保证插入后依然是堆。插入步骤把新元素放到数组末尾完全二叉树最后一个位置对这个新元素执行向上调整直到满足堆性质向上调整代码小堆/** * 小堆向上调整 * param child 新插入节点的下标 */ public void shiftUp(int child) { // 找到父节点 int parent (child - 1) / 2; while (child 0) { // 父节点更小满足堆结束 if (array[parent] array[child]) { break; } // 交换 int temp array[parent]; array[parent] array[child]; array[child] temp; // 继续向上 child parent; parent (child - 1) / 2; } }3.5 堆的删除操作堆的删除规则只能删除堆顶元素优先级最高 / 最低元素删除步骤把堆顶元素和堆最后一个元素交换堆的有效元素个数减 1逻辑删除对新的堆顶执行向下调整恢复堆结构四、手动模拟实现优先级队列MyPriorityQueue结合上面的插入、删除、获取堆顶我们可以写出一个最简可用的优先级队列不考虑复杂扩容public class MyPriorityQueue { // 底层数组存储堆 private int[] array new int[100]; // 有效元素个数 private int size 0; // 入队插入元素 public void offer(int e) { array[size] e; // 插入后向上调整 shiftUp(size - 1); } // 出队删除堆顶并返回 public int poll() { // 保存旧堆顶 int oldTop array[0]; // 最后一个元素放到堆顶 array[0] array[--size]; // 向下调整恢复堆 shiftDown(0); return oldTop; } // 查看堆顶元素不删除 public int peek() { return array[0]; } // 向上调整 private void shiftUp(int child) { // 上文代码 } // 向下调整 private void shiftDown(int parent) { // 上文代码 } }五、Java 官方 PriorityQueue 完整使用指南Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的。Java 内置了开箱即用的优先级队列java.util.PriorityQueue。5.1 PriorityQueue 核心特性必背关于PriorityQueue的使用要注意1. 使用时必须导入PriorityQueue所在的包即import java.util.PriorityQueue;2. PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出ClassCastException异常3. 不能插入null对象否则会抛出NullPointerException4. 没有容量限制可以插入任意多个元素其内部可以自动扩容5. 插入和删除元素的时间复杂度为6. PriorityQueue底层使用了堆数据结构7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素5.2 常用构造方法构造方法说明PriorityQueue()创建空优先级队列默认容量 11PriorityQueue(int initialCapacity)指定初始容量不能小于 1PriorityQueue(Collection? extends E c)使用集合直接创建堆示例public static void testConstruct() { // 默认容量11 PriorityQueueInteger q1 new PriorityQueue(); // 指定容量100 PriorityQueueInteger q2 new PriorityQueue(100); // 用集合创建 ListInteger list Arrays.asList(4,3,2,1); PriorityQueueInteger q3 new PriorityQueue(list); }5.3 常用核心 API方法功能boolean offer(E e)插入元素失败抛异常E peek()获取堆顶空返回 nullE poll()删除堆顶并返回空返回 nullint size()返回有效元素个数void clear()清空队列boolean isEmpty()判断是否为空示例public static void testAPI() { int[] arr {4,1,9,2,8,0,7,3,6,5}; PriorityQueueInteger q new PriorityQueue(arr.length); // 入队 for (int num : arr) { q.offer(num); } System.out.println(q.size()); // 10 System.out.println(q.peek()); // 0小堆堆顶 // 出队两次 q.poll(); q.poll(); System.out.println(q.peek()); // 2 q.offer(0); System.out.println(q.peek()); // 0 q.clear(); System.out.println(q.isEmpty());// true }5.4 如何创建大根堆面试高频默认是小根堆想变成大根堆必须传入自定义比较器Comparator。// 自定义比较器实现大根堆 class IntDescComparator implements ComparatorInteger { Override public int compare(Integer o1, Integer o2) { // 降序o2 - o1 return o2.compareTo(o1); } } public class TestBigHeap { public static void main(String[] args) { PriorityQueueInteger pq new PriorityQueue(new IntDescComparator()); pq.offer(4); pq.offer(3); pq.offer(1); pq.offer(5); // 输出 5大堆堆顶 System.out.println(pq.peek()); } }5.5 JDK 1.8 扩容机制源码级PriorityQueue自动扩容规则private void grow(int minCapacity) { int oldCapacity queue.length; // 容量 642倍扩容≥641.5倍扩容 int newCapacity oldCapacity ((oldCapacity 64) ? (oldCapacity 2) : (oldCapacity 1)); // 超过最大限制时处理 if (newCapacity - MAX_ARRAY_SIZE 0) newCapacity hugeCapacity(minCapacity); queue Arrays.copyOf(queue, newCapacity); }简化总结容量 64→2 倍扩容容量≥ 64→1.5 倍扩容超过Integer.MAX_VALUE - 8→ 按最大容量处理六、堆的三大经典应用6.1 堆排序利用堆实现高效排序时间复杂度 O (nlogn)空间复杂度 O (1)。规则排升序→ 建大堆排降序→ 建小堆步骤把数组建成堆循环交换堆顶与最后一个元素 → 堆大小 - 1 → 向下调整堆顶public void heapSort(){ int endusedSize-1; while(end0){ swap(elem,0,end); shiftDown(0,end);//范围截止到倒数第二个元素 end--; } } public void swap(int[] elem,int i,int j){ int tmpelem[i]; elem[i]elem[j]; elem[j]tmp; } //向下调整的时间复杂度 On private void shiftDown(int parent, int usedSize) { int childparent*21;//右子树 while(childusedSize){ int tmpelem[parent]; //找到左右子树的最大值 if(child1usedSizeelem[child]elem[child1]){ child;//左子树 } if(tmpelem[child]){ elem[parent]elem[child]; elem[child]tmp; parentchild; childparent*21; }else{ break; } } }6.2 Top-K 问题面试 / 笔试最高频最大K个数问题描述在海量数据中找出前 K 个最大 / 最小的数。比如世界 500 强、成绩前 10 名、游戏战力前 100。最优解法堆数据太大无法全部加载到内存时只有堆能高效解决核心思路求前 K 个最大元素→ 建小根堆求前 K 个最小元素→ 建大根堆简单版代码最小 K 个数class Solution { public int[] smallestK(int[] arr, int k) { if (arr null || k 0) { return new int[0]; } PriorityQueueInteger pq new PriorityQueue(); for (int num : arr) { pq.offer(num); } int[] res new int[k]; for (int i 0; i k; i) { res[i] pq.poll(); } return res; } }题目链接https://leetcode.cn/problems/xx4gT2/description/class Solution { public int findKthLargest(int[] nums, int k) { int usedSizenums.length; if(k0||kusedSize){ System.out.println(K越界); return -1; } // 1. 把数组【前k个元素】创建成 小根堆 createSmallHeap(nums,k); // 2. 遍历【从k开始到末尾】的所有元素 for(int ik;iusedSize;i){ // 3. 当前元素 堆顶说明能进前k if(nums[0]nums[i]){ nums[0]nums[i]; shiftDownSmall(nums,0,k); } // 比堆顶小 → 直接跳过不处理 } return nums[0]; // 执行到这里elem[0] ~ elem[k-1] 就是 前k个最大元素 } // 工具方法 // 创建【大小为k】的小根堆 private void createSmallHeap(int[] nums,int k) { for(int i(k-1-1)/2;i0;i--){ shiftDownSmall(nums,i,k); } } // 小根堆 向下调整K-Top专用 private void shiftDownSmall(int[] nums,int parent, int k) { int childparent*21; while(childk){ // 小根堆找到 左右孩子中【更小】的那个 if(child1knums[child]nums[child1]){ child; } // 父节点 孩子 → 交换小的往上浮 if(nums[parent]nums[child]){ swap(nums,parent,child); parentchild; childparent*21; }else { break; } } } public void swap(int[] nums,int i,int j){ int tmpnums[i]; nums[i]nums[j]; nums[j]tmp; } }最小K个数三个方法1.整体排序2.整体建立一个大小为N的小根堆3.把前K个元素创建为大根堆 遍历剩下的N-K个元素和堆顶元素比较如果比堆顶元素小则堆顶元素删除当前元素入堆题目链接https://leetcode.cn/problems/smallest-k-lcci/description/法2.整体建立一个大小为N的小根堆class Solution { public int[] smallestK(int[] arr, int k) { PriorityQueueInteger priorityQueue new PriorityQueue(); for (int i 0; i arr.length; i) { priorityQueue.offer(arr[i]); } int[] ret new int[k]; for(int i0;ik;i){ ret[i]priorityQueue.poll(); } return ret; } }法3.把前K个元素创建为大根堆 遍历剩下的N-K个元素和堆顶元素比较如果比堆顶元素小则堆顶元素删除当前元素入堆class Solution { class IntCmp implements ComparatorInteger{ //IntCmp自定义比较器的名字随便起 //implements实现一个接口 //ComparatorInteger比较器接口专门用来比较 Integer 数字 Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); //先讲 compareTo 是什么? Integer 自带的方法 //a.compareTo(b) //负数a 更小 //0相等 //正数a 更大 //所以 //o1.compareTo(o2) → 升序小在前大在后小根堆默认 //o2.compareTo(o1) → 降序大在前小在后大根堆 } } public int[] smallestK(int[] arr, int k) { int[] retnew int[k]; //把前K个元素创建为大根堆 遍历剩下的N-K个元素和堆顶元素比较如果比堆顶元素小则堆顶元素删除当前元素入堆 if(arrnull||k0){ return ret; } PriorityQueueInteger priorityQueue new PriorityQueue(k,new IntCmp()); for(int i0; ik;i){ priorityQueue.offer(arr[i]); //前K个元素是大根堆 } for(int ik;iarr.length;i){ //遍历剩下的N-K个元素和堆顶元素比较如果比堆顶元素小则堆顶元素删除当前元素入堆 int peekValpriorityQueue.peek(); if(arr[i]peekVal){ priorityQueue.poll(); priorityQueue.offer(arr[i]); } } for(int i0;ik;i){ ret[i]priorityQueue.poll(); } return ret; } }七、配套习题 详细答案习题 1下列关键字序列为堆的是( )A: 100,60,70,50,32,65B: 60,70,65,50,32,100C: 65,100,70,32,50,60D: 70,65,100,32,50,60E: 32,50,100,70,65,60F: 50,100,70,65,60,32答案A解析A 满足大根堆规则父节点均大于等于子节点。习题 2已知小根堆为 8,15,10,21,34,16,12删除关键字 8 之后重建堆关键字之间的比较次数是 ( )A:1 B:2 C:3 D:4答案C删除堆顶 → 交换首尾从根向下调整选孩子1 次父子比较1 次下一层父子比较1 次总共 3 次15 1012 1012 16习题 3最小堆 [0,3,2,5,7,4,6,8]删除堆顶元素 0 之后其结果是 ( )A: [3,2,5,7,4,6,8]B: [2,3,5,7,4,6,8]C: [2,3,4,5,7,8,6]D: [2,3,4,5,6,7,8]答案C习题 4一组记录排序码为 (5,11,7,2,3,17)利用堆排序建立的初始堆为 ( )A: (11,5,7,2,3,17)B: (11,5,7,2,17,3)C: (17,11,7,2,3,5)D: (17,11,7,5,3,2)E: (17,7,11,3,5,2)F: (17,7,11,3,2,5)答案C八、全文总结最强思维导图版优先级队列 按优先级出队底层是堆堆 完全二叉树 顺序存储 父节点与子节点有序堆分两种大根堆、小根堆堆核心操作向下调整O (logn)向上调整O (logn)建堆O (N)JavaPriorityQueue默认小堆不能存 null、元素必须可比较扩容64→2 倍≥64→1.5 倍堆最经典应用堆排序、Top-K 问题总结以上就是今天要讲的内容本文简单记录了java数据结构仅作为一份简单的笔记使用大家根据注释理解您的点赞关注收藏就是对小编最大的鼓励