算法编程题：堆、优先队列与 Top K（5 题）

解题思路： 维护包含当前最大 K 个值的小根堆，超出 K 时移除最小值。

不变量： 扫描后堆中保存已见元素最大的 K 个，堆顶是其中最小值。

public static class AlgCode061Solution
{
    public static int Solve(int[] numbers, int k)
    {
        var heap = new PriorityQueue<int, int>();
        foreach (int value in numbers)
        {
            heap.Enqueue(value, value);
            if (heap.Count > k) heap.Dequeue();
        }
        return heap.Peek();
    }
}

复杂度： 时间 O(n log k)，额外空间 O(k)。

边界用例： k=1；k=n；重复值；负数。

面试追问：

• 快速选择的平均复杂度和最坏复杂度分别是什么？

解题思路： 先统计频次，再用大小为 K 的小根堆保留最高频元素。

不变量： 堆中保存已处理键中频次最高的 K 个，堆顶频次最低。

public static class AlgCode062Solution
{
    public static int[] Solve(int[] numbers, int k)
    {
        var counts = new Dictionary<int, int>();
        foreach (int value in numbers)
            counts[value] = counts.GetValueOrDefault(value) + 1;
        var heap = new PriorityQueue<int, int>();
        foreach ((int value, int count) in counts)
        {
            heap.Enqueue(value, count);
            if (heap.Count > k) heap.Dequeue();
        }
        var result = new int[k];
        for (int index = k - 1; index >= 0; index--)
            result[index] = heap.Dequeue();
        return result;
    }
}

复杂度： 平均时间 O(n + u log k)，额外空间 O(u+k)。

边界用例： k 等于不同值数量；频次相同的结果顺序不作要求。

面试追问：

• 值频次上限为 n 时如何使用桶把时间降到 O(n)？

解题思路： 把每条非空链表头加入小根堆，弹出后加入其后继。

不变量： 堆中最多保存每条链表当前尚未合并的最小节点。

public static class AlgCode063Solution
{
    public sealed class ListNode
    {
        public int Value;
        public ListNode? Next;
        public ListNode(int value, ListNode? next = null)
            => (Value, Next) = (value, next);
    }
    
    public static ListNode? Solve(ListNode?[] lists)
    {
        var heap = new PriorityQueue<ListNode, int>();
        foreach (ListNode? node in lists)
            if (node is not null) heap.Enqueue(node, node.Value);
        var sentinel = new ListNode(0);
        ListNode tail = sentinel;
        while (heap.Count > 0)
        {
            ListNode node = heap.Dequeue();
            tail.Next = node;
            tail = node;
            if (node.Next is not null)
                heap.Enqueue(node.Next, node.Next.Value);
        }
        tail.Next = null;
        return sentinel.Next;
    }
}

复杂度： N 个节点各入堆出堆一次，时间 O(N log k)，额外空间 O(k)。

边界用例： 空数组；全部为空；重复值；只有一条链表。

面试追问：

• 两两分治合并的复杂度和堆方案相比如何？

解题思路： 最大堆保存较小一半，最小堆保存较大一半，并在每次插入后再平衡。

不变量： 两堆大小差不超过一，且 lower 的所有值不大于 upper。

public static class AlgCode064Solution
{
    public sealed class MedianFinder
    {
        private readonly PriorityQueue<int, long> _lower = new();
        private readonly PriorityQueue<int, int> _upper = new();
    
        public void Add(int value)
        {
            if (_lower.Count == 0 || value <= _lower.Peek())
                _lower.Enqueue(value, -(long)value);
            else
                _upper.Enqueue(value, value);
    
            if (_lower.Count > _upper.Count + 1)
            {
                int moved = _lower.Dequeue();
                _upper.Enqueue(moved, moved);
            }
            else if (_upper.Count > _lower.Count)
            {
                int moved = _upper.Dequeue();
                _lower.Enqueue(moved, -(long)moved);
            }
        }
    
        public double FindMedian()
        {
            if (_lower.Count > _upper.Count) return _lower.Peek();
            return ((long)_lower.Peek() + _upper.Peek()) / 2.0;
        }
    }
    
    public static MedianFinder Solve() => new();
}

复杂度： 插入 O(log n)，查询 O(1)，空间 O(n)。

边界用例： 负数；重复值；int.MinValue；偶数个元素求和溢出。

面试追问：

• 如果只需要最近 W 个值的中位数，还需要解决什么删除问题？

解题思路： 最大堆选择剩余次数最多的任务，队列保存尚未冷却完成的任务。

不变量： 堆中任务当前可执行，冷却队列按再次可用时间递增。

public static class AlgCode065Solution
{
    public static int Solve(char[] tasks, int cooldown)
    {
        var counts = new Dictionary<char, int>();
        foreach (char task in tasks)
            counts[task] = counts.GetValueOrDefault(task) + 1;
        var ready = new PriorityQueue<int, int>();
        foreach (int count in counts.Values) ready.Enqueue(count, -count);
        var cooling = new Queue<(int ReadyAt, int Remaining)>();
        int time = 0;
        while (ready.Count > 0 || cooling.Count > 0)
        {
            time++;
            while (cooling.Count > 0 && cooling.Peek().ReadyAt <= time)
            {
                int remaining = cooling.Dequeue().Remaining;
                ready.Enqueue(remaining, -remaining);
            }
            if (ready.Count == 0) continue;
            int next = ready.Dequeue() - 1;
            if (next > 0) cooling.Enqueue((time + cooldown + 1, next));
        }
        return time;
    }
}

复杂度： 时间 O(T log u)，空间 O(u)，T 为包含空闲时间的总时长。

边界用例： 空任务；cooldown=0；单一任务；多任务频次相同。

面试追问：

• 如何用最高频任务的计数公式直接计算答案？