扩展优先队列的稳定性与 Top-N 优化

在数据处理和调度系统中，优先队列是一种核心数据结构。今天我们深入分析一个工业级 扩展优先队列 的实现，探索其 外部优先级 和 Top-N 优化 的设计智慧。

场景与需求

扩展优先队列的应用场景：

任务调度：按优先级执行任务
Top-K 查询：从大量数据中快速获取 Top-K
限流降级：保留高优先级请求

核心需求：

外部优先级：优先级由外部指定，不从元素本身计算
Top-N 优化：只需要维护 Top-N 个元素
稳定性：相同优先级的元素处理顺序

解决方案：扩展优先队列设计

工业级实现采用了巧妙的封装：

// 核心设计：封装标准库的优先级队列
template <class T, class TPriority = int>
class TExtPriorityQueue {
    // 允许外部指定优先级
    void push(const T& data, const TPriority priority);
    const T& ytop() const { return TBase::top().Data; }
};

// Top-N 优化版本
template <class T, class TPriority = int>
class TPriorityTopN {
    size_t N = 0;
    TMaybe<TPriority> LastShifted;
    
    void push(const T& data, const TPriority priority) {
        if (size() < N || priority > top().Pri) {
            TBase::push(data, priority);
            if (size() > N) {
                LastShifted = top().Pri;
                TBase::pop();
            }
        }
    }
};

核心设计

外部优先级
- 元素本身不包含优先级
- 推送时单独指定优先级
- 增加了灵活性
Top-N 优化
- 只维护 N 个最高优先级元素
- 超过 N 时弹出最低优先级
- 空间复杂度 O(N)

边界收缩

void ShrinkToSharpBorder() {
    while (!empty() && top().Pri == LastShifted.GetRef()) {
        pop();
    }
}

权衡分析

优点

灵活性：支持外部指定优先级
空间优化：Top-N 版本只需 O(N) 空间
性能：避免维护整个数据集

代价

不稳定性：相同优先级元素顺序不确定
复杂度：边界收缩逻辑复杂
精度：可能丢失部分数据

适用场景

只需要 Top-K 场景
内存受限但数据量大
优先级动态计算

净室重构：Go 实现

下面用 Go 展示同样的设计思想：

// ExtPriorityQueue: 支持外部优先级
type ExtPriorityQueue struct {
    pq PriorityQueue
}

func (q *ExtPriorityQueue) Push(value string, priority int) {
    heap.Push(&q.pq, Item{value, priority})
}

func (q *ExtPriorityQueue) Pop() string {
    return heap.Pop(&q.pq).(Item).value
}

// PriorityTopN: 只维护 Top-N
type PriorityTopN struct {
    pq PriorityQueue
    N  int
}

func (ptn *PriorityTopN) Push(value string, priority int) {
    if ptn.pq.Len() < ptn.N {
        heap.Push(&ptn.pq, Item{value, priority})
    } else if priority > ptn.pq[0].priority {
        heap.Pop(&ptn.pq)
        heap.Push(&ptn.pq, Item{value, priority})
    }
}

运行结果验证了设计：

=== Extended Priority Queue Demo (Go) ===

--- Test 1: ExtPriorityQueue ---
Size: 3
Top: task1
Pop: task1
Pop: task3
Pop: task2

--- Test 2: PriorityTopN ---
After push 'a'(10): size=1, top=a
After push 'b'(20): size=2, top=b
After push 'e'(25): size=3, top=e

总结

扩展优先队列的设计体现了 灵活性与效率的平衡：

外部优先级：解耦元素与优先级
Top-N 优化：空间换时间
边界收缩：处理边界情况
稳定性考虑：ShrinkToSharpBorder

这种设计不是"银弹"，但对于 Top-K 场景，是一个非常优雅的权衡选择。