教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文围绕《AlgoNote 算法通关手册》中 LeetCode 0973. 最接近原点的 K 个点 这一题解展开题目要求从平面点集points中找出距离原点(0, 0)最近的K个点本质上是典型的Top-K 最小问题。文章以「手写小顶堆构建优先队列」为绝对主线逐行拆解Heapq类的heapAdjust / heapify / heappush / heappop五个核心方法并结合仓库中 03_04_priority_queue.md、01_09_array_heap_sort.md 等章节与codes/python/01_array/array_maxheap.py、array_sort_minheap_sort.py等源码交叉印证堆的底层原理随后给出基于heapq标准库的简化实现、小顶堆与大顶堆两种思路的复杂度对比、快速选择分治与排序等延伸解法以及同主题题目串讲。读完本文你将掌握「用堆解决 Top-K 最近/最大/最小问题」的完整套路并能将其迁移到 0215. 数组中的第K个最大元素、LCR 159. 库存管理 III、0347. 前 K 个高频元素 等同类题目上。一、题目速览与问题拆解题目链接0973. 最接近原点的 K 个点 - 力扣标签几何、数组、数学、分治、快速选择、排序、堆优先队列难度中等题目大意给定一个由平面上的点组成的列表points再给定一个整数K要求从中找出K个距离原点(0, 0)最近的点。这里平面上两点之间的距离是欧几里德距离即 $\sqrt{(x_1-x_2)^2 (y_1-y_2)^2}$。答案可以按任何顺序返回除了点坐标的顺序之外答案确保是唯一的。示例输入: points [[1,3],[-2,2]], K 1 输出: [[-2,2]] 输入: points [[3,3],[5,-1],[-2,4]], K 2 输出: [[3,3],[-2,4]] # 答案按任何顺序返回均可1.1 问题的数学化与「距离比较」优化由于只比较相对远近且平方根函数单调递增比较两点到原点距离时可以省略开方直接用「距离平方」作为排序键dist point[0] * point[0] point[1] * point[1]这正是本题题解代码中Heapq.compare()方法的实现依据。用平方距离代替欧几里德距离既不影响大小关系又避免了浮点运算这也是计算几何题目中常见的优化手法。1.2 问题定位Top-K 问题家族「取最近 K 个点」本质上就是Top-K最小问题从 $n$ 个元素中选出最小的 $K$ 个。它与 0215. 数组中的第K个最大元素Top-K 最大、LCR 159. 库存管理 III最小的 K 个数属于同一类问题可以用排序、堆、快速选择三种思路解决。本文按仓库题解的原始脉络重点讲解堆优先队列解法。二、核心思路用小顶堆构建优先队列题解给出的解题思路分三步使用二叉堆构建优先队列优先级为「距离原点的距离」此时堆顶元素即为距离原点最近的元素将堆顶元素加入答案数组执行出队操作时间复杂度 $O(\log n)$出队时交换堆顶元素与末尾元素将末尾元素移出堆再继续调整小顶堆不断重复第 2 步直到进行K次结束。三步流程可以用下图表示points 列表 │ 逐点 heappush 入堆每步 O(log n) ▼ 小顶堆 queue堆顶 距原点最近的点 │ 重复 K 次 heappop每步 O(log n) ▼ 答案数组 res含 K 个最近点2.1 为什么选「小顶堆」而不是「大顶堆」小顶堆思路本文题解堆顶永远是最小元素。把所有 $n$ 个点全部入堆后heappop弹出的就是最近的点连续弹出K次即得到答案。建堆总复杂度 $O(n)$基于heapify每次弹出 $O(\log n)$总复杂度 $O(n K\log n)$。大顶堆思路推荐实现只维护大小为K的堆堆顶是「当前 K 个最近点中距离最大的那个」。遍历每个点时若新点比堆顶更近则替换堆顶并调整堆。这样空间复杂度从 $O(n)$ 降到 $O(K)$总复杂度为 $O(n\log K)$在 $K$ 远小于 $n$ 时更优。该思路与 LCR 159. 库存管理 III 的「大顶堆维护前 K 小」做法完全同构。两种思路的对比如下方案堆类型空间复杂度时间复杂度全量入小顶堆弹 K 次小顶堆$O(n)$$O(n K\log n)$维护大小为 K 的大顶堆大顶堆$O(K)$$O(n\log K)$三、题解源码逐行精讲手写 Heapq 小顶堆本题题解完整给出了一版手写二叉堆实现见 k-closest-points-to-origin.md。其核心是Heapq类中的五个方法。以下代码与仓库原文保持一致注释结合源码进一步细化。3.1 比较器以距离平方为优先级class Heapq: def compare(self, a, b): dist_a a[0] * a[0] a[1] * a[1] dist_b b[0] * b[0] b[1] * b[1] if dist_a dist_b: return -1 elif dist_a dist_b: return 0 else: return 1compare(a, b)返回-1 / 0 / 1语义等价于 Python 内置的__lt__比较当a距原点更近时返回-1优先级更高。后续所有堆调整都通过这个比较器判断大小关系这样就把「比较点」这一业务逻辑与「堆结构维护」解耦可以无缝替换为其他比较规则如按频率比较即可解 0347. 前 K 个高频元素。3.2 堆调整 heapAdjust下移调整维护小顶堆# 堆调整方法调整为小顶堆 def heapAdjust(self, nums: [int], index: int, end: int): left index * 2 1 right left 1 while left end: # 当前节点为非叶子结点 max_index index if self.compare(nums[left], nums[max_index]) -1: max_index left if right end and self.compare(nums[right], nums[max_index]) -1: max_index right if index max_index: # 如果不用交换则说明已经交换结束 break nums[index], nums[max_index] nums[max_index], nums[index] # 继续调整子树 index max_index left index * 2 1 right left 1这段代码与仓库中 03_04_priority_queue.md 第 3.4 节手写Heapq的heapAdjust结构一致只是把大顶堆的大小比较nums[left] nums[max_index]换成了小顶堆的距离比较self.compare(...) -1。要点解读利用数组存储完全二叉树的下标关系节点下标为index左孩子为2*index1右孩子为2*index2end是当前堆的最后一个有效元素下标right end用于防止右孩子越界在「根 / 左孩子 / 右孩子」三者中找出距离最小的那个max_index名称沿用了大顶堆实现的命名实际语义是「最小优先级下标」若根节点本身就是最小者则break否则交换根与最小孩子并下沉继续调整子树单次调整的时间复杂度为 $O(\log n)$最坏沿树高下沉。3.3 建堆 heapify# 将数组构建为二叉堆 def heapify(self, nums: [int]): size len(nums) # (size - 2) // 2 是最后一个非叶节点叶节点不用调整 for i in range((size - 2) // 2, -1, -1): # 调用调整堆函数 self.heapAdjust(nums, i, size - 1)从最后一个非叶节点(size-2)//2开始自底向上对每个节点执行heapAdjust即可在线性时间内把任意数组调整为小顶堆建堆总代价 $O(n)$。这与 01_09_array_heap_sort.md 中「第一阶段构建初始大顶堆」的代码骨架完全相同仅堆序方向相反。3.4 入队 heappush上移调整# 入队操作 def heappush(self, nums: list, value): nums.append(value) size len(nums) i size - 1 # 寻找插入位置 while (i - 1) // 2 0: cur_root (i - 1) // 2 # value 大于当前根节点则插入到当前位置 if self.compare(nums[cur_root], value) -1: break # 继续向上查找 nums[i] nums[cur_root] i cur_root # 找到插入位置或者到达根位置将其插入 nums[i] value入队分两步先把新元素追加到数组末尾再沿父节点链自下而上「上移」——只要父节点比新元素更近compare(nums[cur_root], value) -1说明新元素该停在当前位置循环结束否则父节点下移继续向根方向查找插入位。最坏情况从叶子爬到根复杂度 $O(\log n)$。仓库中 queue_priority_queue.py 的大顶堆版heappush与此互为镜像。3.5 出队 heappop交换堆顶与末尾再下移# 出队操作 def heappop(self, nums: list) - int: size len(nums) nums[0], nums[-1] nums[-1], nums[0] # 得到最小值堆顶元素然后调整堆 top nums.pop() if size 0: self.heapAdjust(nums, 0, size - 2) return top出队是入队的逆过程也是题解解题思路第 2 步所指的「交换堆顶元素与末尾元素将末尾元素移出堆继续调整小顶堆」把堆顶最近点与末尾元素交换pop()弹出末尾元素即拿到堆顶目标值对新堆顶执行一次heapAdjust下移调整恢复小顶堆性质注意调整范围为0到size - 2即弹出后的新堆。复杂度 $O(\log n)$。3.6 堆排序 heapSort题解附带便于理解堆的全局行为# 升序堆排序 def heapSort(self, nums: [int]): self.heapify(nums) size len(nums) for i in range(size): nums[0], nums[size - i - 1] nums[size - i - 1], nums[0] self.heapAdjust(nums, 0, size - i - 2) return nums先建堆再反复「交换堆顶与末尾 缩小堆范围 下移调整」得到升序序列。它与 array_sort_minheap_sort.py 中MinHeap.minHeapSort的过程一致小顶堆每次取出的都是最小值交换到末尾后得到升序数组。3.7 Solution 主流程class Solution: def kClosest(self, points: List[List[int]], k: int) - List[List[int]]: heap Heapq() queue [] for point in points: heap.heappush(queue, point) res [] for i in range(k): res.append(heap.heappop(queue)) return res主流程非常简洁全部点入小顶堆 → 连续出队K次。注意kClosest中k即题目的KList来自typing。四、从手写堆到 heapq两种工程化实现4.1 基于 heapq 标准库的极简实现仓库 03_04_priority_queue.md 第 3.5 节指出Python 标准库heapq模块实现了高效的最小堆heapq.heappush(heap, item)入队、heapq.heappop(heap)弹出最小元素。据此本题可以改写为import heapq from typing import List class Solution: def kClosest(self, points: List[List[int]], k: int) - List[List[int]]: # 以 (距离平方, x, y) 作为堆元素heapq 默认小顶堆距离最小者优先 heap [(x * x y * y, x, y) for x, y in points] heapq.heapify(heap) # 线性建堆 O(n) return [[x, y] for _, x, y in heapq.nsmallest(k, heap)]若希望严格按「弹出 K 次」的思路可直接循环heapq.heappop(heap)共k次而heapq.nsmallest(k, heap)内部同样基于堆完成。使用heapq时无需关心heapAdjust / heapify / heappush / heappop的手写细节因为标准库已经封装好。4.2 推荐面试实现大小为 K 的大顶堆空间 O(K)本题标签中包含「堆优先队列」面试中更推荐的方案是维护大小为K的大顶堆逻辑与 LCR 159. 库存管理 III 思路 1大顶堆取最小的 k 个数完全一致。由于 Pythonheapq默认是小顶堆实现大顶堆的惯用技巧是将距离平方取负数存入堆中import heapq from typing import List class Solution: def kClosest(self, points: List[List[int]], k: int) - List[List[int]]: heap [] # 维护「负距离平方」的小顶堆等价于距离平方的大顶堆 for x, y in points: dist -(x * x y * y) # 取负距离越远堆值越小 if len(heap) k: heapq.heappush(heap, (dist, x, y)) # 堆未满直接入堆 elif dist heap[0][0]: # 当前点比堆顶K 个最近点中最远的更近 heapq.heapreplace(heap, (dist, x, y)) # 弹出最远点并插入当前点 return [[x, y] for _, x, y in heap]要点堆元素是三元组(负距离平方, x, y)heapq在元组上先比较第一元素因此堆顶始终是「当前 K 个最近点中距离最大」的点heapreplace等价于「先heappop再heappush」且更高效空间复杂度 $O(K)$时间复杂度 $O(n\log K)$。五、复杂度分析与思路对比解法时间复杂度空间复杂度说明排序后取前 K 个$O(n\log n)$$O(1)$原地实现最简单但做了大量无用排序全量小顶堆弹 K 次本题题解$O(n K\log n)$$O(n)$建堆 $O(n)$每次弹出 $O(\log n)$大小为 K 的大顶堆$O(n\log K)$$O(K)$数据流式处理适合 $K \ll n$ 与在线场景快速选择分治期望 $O(n)$$O(\log n)$递归栈见下文第六节其中「全量小顶堆」的建堆之所以是 $O(n)$ 而非 $O(n\log n)$正是因为heapify从最后一个非叶节点自底向上调整第 $i$ 层每个节点的下移代价最多 $(\log n - i)$求和后为线性量级这一推导在 01_09_array_heap_sort.md 第 2.4 节中有详细展开。六、延伸解法快速选择与排序6.1 快速选择分治本题标签包含「分治、快速选择」。快速排序的每次partition都会确定一个元素的最终位置并以此为界把数组分为左右两个子数组据此只需在目标区间递归与答案无关的区间可以整体忽略从而把平均复杂度降到 $O(n)$。这正是 0215. 数组中的第K个最大元素 思路 2 的做法随机挑选基准数randomPartition避免最坏情况当基准位置恰好等于目标下标时即返回。把该思路应用到本题只需将比较键换成距离平方并寻找「第 K 小」位置。LCR 159. 库存管理 III 思路 2 给出了更贴近本题的模板当partition返回的基准位置pi k时直接返回arr[:k]pi k递归左区间pi k递归右区间。读者可将其中的比较逻辑从整数值换成距离平方即可得到本题的快速选择版本。该思路期望时间复杂度 $O(n)$证明可参考算法导论 9.2 节「期望为线性的选择算法」空间复杂度 $O(\log n)$递归栈。6.2 直接排序不推荐用于本题最朴素的做法是把points按距离平方升序排序后取前K个时间复杂度 $O(n\log n)$。这种做法适合时间紧迫时快速提交但本题作为 Top-K 经典题面试中更期待堆或快速选择解法0215 思路 3 对「借用标准库 sort」同样标注为「不建议」。七、相关题目串讲把堆解法迁移到其他 Top-K 题0215. 数组中的第K个最大元素维护大小为K的小顶堆heapq堆顶即为第 K 大时间复杂度 $O(n\log K)$也可用大顶堆全量排序或快速选择。与本题互为「最大/最小」镜像。LCR 159. 库存管理 III返回最小的 K 个数用大顶堆维护前 K 小代码骨架buildMaxHeap 遍历替换与本文 4.2 节完全同构可对比阅读。0347. 前 K 个高频元素先用哈希表统计频数再以频数为优先级用大顶堆出队 K 次。其题解中的Heapq类与本文手写堆几乎一致仅把比较器从「距离平方」换成「频数」——这再次印证了本文 3.1 节将比较逻辑独立封装的价值。八、仓库中的配套学习资源优先队列与手写堆的系统讲解03_04_priority_queue.md含大顶堆版Heapq手写实现、heapq模块用法、滑动窗口最大值例题堆排序与堆操作原理01_09_array_heap_sort.md含堆定义、数组存储下标公式、上移/下移调整、复杂度分析可运行源码array_maxheap.py大顶堆MaxHeap的push / pop / peek完整实现array_sort_minheap_sort.py小顶堆建堆与堆排序实现queue_priority_queue.py大顶堆版优先队列入队/出队/堆排序题目总览00_05_solutions_list.md第 967 行收录本题、00_06_categories_list.md优先队列题目分类、0900-0999 目录读者可将本文 3.7 节的Solution.kClosest与 4.2 节的heapq版本分别在本机 Python 3 环境中运行验证对points [[1,3],[-2,2]], k 1应得到[[-2,2]]对points [[3,3],[5,-1],[-2,4]], k 2应得到距离平方为 18 与 20 的两个点。文中所有代码均可在任意 Python 3 环境直接执行无需额外依赖。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AzerothCore-WoTLK 实战两条 Docker 命令起一个可登录的魔兽 3.3.5 私服AzerothCore WoTLK 实战两条 Docker 命令起一个可登录的魔兽 3.3.5 私服 AzerothCore WoTLK 是面向魔兽世界 3.游戏开发后端LeetCode 0632 最小区间覆盖 K 个列表题解AlgoNote 算法通关手册的堆优先队列实战解析LeetCode 0632 最小区间覆盖 K 个列表题解AlgoNote 算法通关手册的堆优先队列实战解析 导读 本题是「 AlgoNote 算法通关教程文档知识库AlgoNote 算法通关手册LeetCode 23 合并 K 个升序链表分治 堆优先队列双解法深度解析AlgoNote 算法通关手册LeetCode 23 合并 K 个升序链表分治 堆优先队列双解法深度解析 本篇以《算法通关手册》AlgoNote中教程文档知识库上一篇【亲测免费】 JupyterLab 变量检查器安装与使用指南下一篇React Big Calendar 使用教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考