新闻详情

新闻详情

首页 / 资讯中心 / 详情

##堆(优先级队列)的部分知识点##

发布时间:2026/9/26 7:10:53来源:尧图网络
##堆(优先级队列)的部分知识点##
一、堆的基本概念堆本质上是一种特殊结构、特殊要求的二叉树其主要用途是作为带有优先级的队列。堆是一个完全二叉树同时满足以下两个要求任意一个父节点的值都大于两个子节点整个树的根节点就是整体最大值大堆。任意一个父节点的值都小于两个子节点整个树的根节点就是整体最小值小堆。面试常问角度堆与普通二叉树的区别是什么为什么堆必须用完全二叉树实现二、堆的存储方式把整棵树层序遍历其结果放入数组中此时arr[0]就是根节点。已知父节点的下标是i已知子节点下标为i左子树下标为2i 1右子树下标为2i 2。父节点下标为(i - 1) / 2。易错点提示下标推导时注意区分「已知父节点求子节点」和「已知子节点求父节点」两组公式不要混淆。三、堆的创建和实现1. 向下调整适用场景整棵树除了根节点以外都已经符合堆的要求只差根节点自己不符合要求。代码实现// 向下调整 public static void shiftDown(int[] arr, int size, int subRoot) { int parent subRoot; int child parent * 2 1; while (child size) { // 选出左右孩子中较大的一个 if (child 1 size arr[child] arr[child 1]) { child child 1; } // 如果父节点已经大于等于较大的孩子则调整结束 if (arr[parent] arr[child]) { break; } // 否则交换父节点与较大的孩子 int tmp arr[child]; arr[child] arr[parent]; arr[parent] tmp; // 继续向下调整 parent child; child parent * 2 1; } }时间复杂度O(log n)空间复杂度O(1)。易错点提示原代码中parent child * 2 1; child parent;的更新顺序写反了会导致死循环或越界。正确写法是先更新parent child再计算新的child parent * 2 1。2. 向上调整适用场景只有当前节点不符合堆的要求。代码实现// 向上调整 public static void shiftUp(int[] arr, int child) { int parent (child - 1) / 2; while (child 0) { // 如果当前节点大于父节点则交换 if (arr[child] arr[parent]) { int tmp arr[child]; arr[child] arr[parent]; arr[parent] tmp; } else { // 已经满足堆的性质提前结束 break; } // 继续向上调整 child parent; parent (child - 1) / 2; } }时间复杂度O(log n)空间复杂度O(1)。理由说明向上调整每次只沿一条从叶子到根的路径进行路径长度不超过树的高度log n因此时间复杂度为O(log n)整个过程只使用常数个临时变量因此空间复杂度为O(1)。易错点提示原代码中if (arr[child] arr[parent])的比较方向写反了这是小堆的写法且交换后缺少else break分支会导致不必要的继续循环。向上调整的终止条件是child 0或当前节点已满足堆的性质。3. 创建堆代码思路基于向下调整实现。找到最后一个非叶子节点(size - 1 - 1) / 2从该节点开始向下调整调整完毕之后都往前走一步。代码实现// 创建堆 public static void createHeap(int[] arr, int size) { // 从最后一个非叶子节点开始向前逐个向下调整 for (int root (size - 1 - 1) / 2; root 0; root--) { shiftDown(arr, size, root); } }时间复杂度O(n)空间复杂度O(1)迭代。易错点提示原代码中for (int root size - 1 - 1; root 0; root--)有两个错误一是循环条件应为root 0否则下标为 0 的根节点不会被调整二是方法名creatHeap拼写错误应为createHeap。4. 插入元素入队列代码思路新元素进行尾插从新元素开始向上调整。代码实现public static int add(int[] arr, int size, int val) { if (size arr.length) { throw new RuntimeException(堆已满无法插入); } arr[size] val; size; shiftUp(arr, size - 1); return size; }时间复杂度O(log n)空间复杂度O(1)迭代。面试常问角度为什么插入操作的时间复杂度是 O(log n)如果数组扩容空间复杂度会变成多少5. 删除堆顶元素出队列代码思路直接用数组的最后一个元素代替根节点的位置同时size--然后从根节点开始向下调整。代码实现// 删除堆顶元素 public static int remove(int[] arr, int size) { if (size 0) { throw new RuntimeException(堆为空无法删除); } int top arr[0]; // 用最后一个元素代替堆顶元素 arr[0] arr[size - 1]; size--; // 进行向下调整 shiftDown(arr, size, 0); return top; }时间复杂度O(log n)空间复杂度O(1)迭代。易错点提示原代码中remove方法返回的是size删除后的元素个数而不是被删除的堆顶元素值这在语义上是错误的。正确做法是先用临时变量保存arr[0]调整完成后返回该值。四、Comparable 和 Comparator 的实现和区别1. 回调函数不需要我们自己主动调用而是交给别人让他们在合适的时机进行调用。面试常问角度回调函数在 Java 集合框架中还有哪些应用场景2. Comparator 的实例化和实现代码实现PriorityQueueInteger queue new PriorityQueue(new IntComparator());class IntComparator implements ComparatorInteger { Override public int compare(Integer o1, Integer o2) { return o2 - o1; // 降序 } } // 在 compare 中 O1-O2 -- 返回升序小的值先出去 // O2-O1 -- 返回降序大的值先出去 // O1O2 -- 返回 0易错点提示当o1 - o2可能溢出时如Integer.MAX_VALUE - (-1)应使用Integer.compare(o1, o2)或o1.compareTo(o2)代替直接相减。3. Comparable 的实例化和实现代码实现PriorityQueueInteger queue new PriorityQueue();class MyInt implements ComparableMyInt { int value; public MyInt(int value) { this.value value; } Override public int compareTo(MyInt other) { return this.value - other.value; // 注意这是升序降序反着减 } }面试常问角度Comparable 和 Comparator 的核心区别是什么什么时候用哪一个4. 两者的区别Comparable 中的compareTo只能实现唯一的一种比较规则Comparator 中的compare可适应多种比较规则可以定义多种比较器。5. 选择建议如果只有一套比较规则用Comparable如果有多套比较规则用Comparator。面试常问角度为什么说 Comparator 比 Comparable 更灵活在排序算法中如何动态切换比较器
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

Win11识别iPhone失败的底层原因与精准修复方案 2026/9/26 7:48:54

Win11识别iPhone失败的底层原因与精准修复方案

1. 这不是iPhone坏了,是Win11和Apple设备应用之间“没对上暗号”你把iPhone用原装USB线插进Win11电脑,屏幕弹出“信任此电脑”提示,你点了“信任”,但Windows右下角通知栏里那个新装的“Apple设备”应用图标——就是那个绿色叶子形…

阅读更多 →
Humanizer 数字本地化转换器契约:INumberToWordsConverter 接口深度解析与自定义实现指南 2026/9/26 7:48:54

Humanizer 数字本地化转换器契约:INumberToWordsConverter 接口深度解析与自定义实现指南

开发工具 【免费下载链接】Humanizer Humanizer meets all your .NET needs for manipulating and displaying strings, enums, dates, times, timespans, numbers and quantities 项目地址: https://gitcode.com/gh_mirrors/hu/Humanizer 点击查看 免费下载 INumb…

阅读更多 →
AI Agent技能安全实战:OpenClaw Skills风险拆解与五层防护 2026/9/26 7:48:54

AI Agent技能安全实战:OpenClaw Skills风险拆解与五层防护

1. 从一次技能调用失控说起:AI Agent 的安全边界到底在哪AI Agent 这两年被讨论得很多,从“帮我订机票”到“自动写代码并提交 PR”,能力边界不断外扩。但真正让一线开发者夜里睡不踏实的,往往不是模型答得对不对,而是…

阅读更多 →
华为云CodeArts实测:代码智能体与CodeBase如何一键生成安全大屏 2026/9/26 7:48:54

华为云CodeArts实测:代码智能体与CodeBase如何一键生成安全大屏

1. 从一条热搜说起:华为云入局AI编程到底意味着什么华为云入局AI编程这件事,其实在开发者圈子里已经发酵了一段时间。CodeArts这个品牌本身不新,它脱胎于华为内部多年的研发工具链积累,从代码托管、流水线、代码检查到测试管理&am…

阅读更多 →
盘立方软件指标文华期货ma均线交叉指标 2026/9/26 7:48:54

盘立方软件指标文华期货ma均线交叉指标

110,COLORBLACK; 0,COLORBLACK; VAR26:(CLOSE-LLV(LOW,30))/(HHV(HIGH,30)-LLV(LOW,30))*100; VAR27:REVERSE(VAR26); VAR28:SMA(VAR26,3,1); 神通:SMA(VAR28,3,1),COLORCYAN; 标王:SMA(神通,3,1),COLORYELLOW; DRAWTEXT(CROSS(神通,标王) AND 神通<40,100,公),COLORWHITE; …

阅读更多 →
libimobiledevice 内部 SRP6a-sha512 客户端认证库剖析:从斯坦福 SRP 裁剪到 iOS 配对实战 2026/9/26 7:48:47

libimobiledevice 内部 SRP6a-sha512 客户端认证库剖析:从斯坦福 SRP 裁剪到 iOS 配对实战

移动开发 【免费下载链接】libimobiledevice A cross-platform protocol library to communicate with iOS devices 项目地址&#xff1a; https://gitcode.com/gh_mirrors/li/libimobiledevice 点击查看 免费下载 libimobiledevice 是跨平台的 iOS 设备通信协议库&#xff0c…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉