第6章｜二分、堆与优先队列

Unit 09 · LeetCode #973 · 状态依赖训练版

← Unit 08 仅本次页面有效

973

K Closest PointsGeometry · Heap · Frontier

已恢复上次学习位置

保留最小的 K 个优先级时，
堆顶要暴露“最坏的保留者”。

Unit 08 已经建立了“候选＋优先级＋Top-K 边界”。本单元只改变保留方向：频率题保留最大优先级，最近点保留最小优先级。真正决定堆方向的不是“第 K 大/小”字面，而是超过容量时应该最先淘汰谁。

原题建模与本单元能力桥梁题面转述、几何优先级、堆方向

题目要求

给定二维点数组 points 和整数 k，返回距离原点最近的 k 个点。结果顺序任意。

class Solution: def kClosest( self, points: List[List[int]], k: int ) -> List[List[int]]: pass

关键约束

1 ≤ k ≤ points.length ≤ 10⁴
坐标范围为 [-10⁴,10⁴]

官方示例

points = [[1,3],[-2,2]], k = 1
输出：[[-2,2]]

points = [[3,3],[5,-1],[-2,4]], k = 2
输出：[[3,3],[-2,4]]

认知桥梁

Unit 08：保留最高频 K 个，根暴露最低频边界。

Unit 09：保留最近 K 个，根暴露最远距离边界。

优先级函数

d²=x²+y²。平方根严格递增，所以无需计算浮点距离。

最坏保留者

最近 K 个点中，距离最大的那个最可能被新点替换。

负优先级

Python 最小堆存 -d²，使真实距离最大的点位于根。

前沿迁移

#23 不再保留固定 Top-K，而是维护每条链表当前暴露的一个候选。

教学点集，k=3点击点，生成当前距离证据

二维坐标系

点与平方距离

概念最大堆：根是最远边界

保留区与淘汰区

当前保留

已淘汰

当前证据

当前不变量

距离排名	点	d²	状态

插入与淘汰记录

当前点—

当前 d²—

根部边界—

当前保留集合[]

核心不变量

当前决策依据

已处理点数0

堆容量 K3

当前堆大小0

本轮淘汰点—

最远保留 d²—

同一个 Top-K 骨架，保留方向决定根部边界

不是看到“最近”就机械使用最小堆；应先问超过容量时谁最该被删除。

表示错误与堆方向错误会分别破坏算法

平方距离决定优先级，负号决定根部方向，坐标字段负责恢复结果。

正距离最小堆限 K

超容量会弹出最近点，最终留下最远 K 个。

只存负距离

最终无法恢复对应坐标，priority 与 payload 必须同时保存。

把堆数组当排序结果

堆只保证根部边界，不保证其余位置完整有序。

边界场景仍由同一不变量覆盖

负坐标会在平方中消除符号；同距离时可用坐标或唯一序号打破元组比较平局。

k=1
只保留当前最近点

k=n
所有点都被保留

相同 d²
结果顺序任意

补全提交代码只提供分层提示，不展示完整答案

class Solution:

def kClosest(self, points, k):

heap = []

for x, y in points:

distance =

if len(heap) > k:

return [

for negative_distance, x, y in heap

]

策略边界：大小 K 最大堆的时间为 O(n log k)、空间 O(k)，适合 k 远小于 n 且不希望修改输入。排序更简单；Quickselect 平均 O(n)，但最坏可退化。

代码—坐标—负距离—淘汰边界联动必须完整播放才可作为迁移解锁路径

class Solution:
    def kClosest(self, points, k):
        heap = []
        for x, y in points:
            distance = x*x + y*y
            heappush(heap, (-distance,x,y))
            if len(heap) > k:
                heappop(heap)
        return [[x,y] for _,x,y in heap]

迁移门槛主代码全部正确，或完整播放主轨迹后解锁。提示与骨架不计为掌握。

迁移题：LeetCode #23《合并 K 个升序链表》

固定 Top-K 堆变为动态候选前沿：每条非空链表最多向堆暴露一个头结点。弹出最小头结点后，只补入同一条链表的后继。

打开官方原题 ↗

1. 官方读题

2. 结构排序

3. 语义槽位

4. 样例与重写

官方任务

给定 K 条已经升序排列的链表，将它们合并为一条升序链表。

输入：
[[1,4,5],
 [1,3,4],
 [2,6]]

输出：
[1,1,2,3,4,4,5,6]

约束与前沿含义

K 可以为 0，空输入返回空链表。
所有链表节点总数不超过 10⁴。
每条链表内部升序，因此其头结点是该链表尚未合并部分的最小值。
堆大小最多为非空链表数量 K。

读题检查 1：为什么初始堆只需要放每条非空链表的头结点？

读题检查 2：两个头结点值相同时，为什么记录中还需要 list_index？

#973 → #23 结构对照

#973 候选
所有点逐个到达
优先级=d²

#973 根部
最远保留点
超过 K 时淘汰

#23 候选
每条链表当前头
优先级=node.val

#23 根部
全局最小前沿
弹出后补后继

按依赖关系点击五个步骤

尚未选择步骤。

槽位 1｜堆记录

槽位 2｜主循环

槽位 3｜接入结果链表

槽位 4｜推进前沿

三条链表与当前前沿

已合并输出

最小堆前沿

独立重写

完整运行官方样例后开放编辑器。这里不提供完整答案，也不提供一键填入。

第6章 Unit 09 Skill 卡

你已经把“固定容量 Top-K 边界”迁移为“动态 K 路候选前沿”：堆的本质不是保存所有数据，而是持续暴露当前决策所需的最优或最坏边界。

几何优先级d²=x²+y²，不计算 sqrt

堆方向根表示保留集合中下一位最应淘汰者

Python 表示(-d²,x,y) 模拟最大堆

Top-K 不变量旧保留集合＋新候选，删除最坏者

K 路前沿每条非空链表最多一个头结点在堆中

平局处理使用 list_index 避免直接比较 ListNode

#23 更新pop 最小节点→接入结果→push 后继

复杂度#973 O(n log k)；#23 O(N log K)

下一单元继续训练 K 路归并与优先队列前沿