Extended Priority Queue: Stability and Top-N Optimization

In data processing and scheduling systems, priority queue is a core data structure. Today we dive into an industrial-grade extended priority queue implementation, exploring its external priority and Top-N optimization design wisdom.

Scenarios and Requirements

Extended priority queue application scenarios:

• Task scheduling: Execute tasks by priority
• Top-K queries: Quickly get Top-K from large datasets
• Rate limiting: Keep high-priority requests

Core requirements:

• External priority: Priority specified externally, not computed from element itself
• Top-N optimization: Only maintain Top-N elements
• Stability: Handle elements with same priority in order

Solution: Extended Priority Queue Design

The industrial implementation uses clever wrapper:

// Core design: wrap standard library priority queue
template <class T, class TPriority = int>
class TExtPriorityQueue {
    // Allow external priority specification
    void push(const T& data, const TPriority priority);
    const T& ytop() const { return TBase::top().Data; }
};

// Top-N optimized version
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();
            }
        }
    }
};

Core Design

1. External Priority

   • Element itself doesn't contain priority
   • Priority specified separately when pushing
   • Increases flexibility

2. Top-N Optimization

   • Only maintain N highest priority elements
   • When exceeding N, pop lowest priority
   • Space complexity O(N)

3. Border Shrinking

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

Trade-off Analysis

Advantages

1. Flexibility: Support external priority specification
2. Space optimization: Top-N version only needs O(N) space
3. Performance: Avoid maintaining entire dataset

Costs

1. Unstability: Elements with same priority have uncertain order
2. Complexity: Border shrinking logic complex
3. Precision: May lose some data

Use Cases

• Top-K scenarios only
• Memory constrained but large data
• Dynamically computed priority

Clean Room Reimplementation: Go Implementation

Here's the same design philosophy demonstrated in Go:

// ExtPriorityQueue: supports external priority
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: maintain only 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})
    }
}

The output validates the design:

=== 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

Summary

Extended priority queue design embodies flexibility + efficiency balance:

1. External priority: Decouple element from priority
2. Top-N optimization: Trade space for time
3. Border shrinking: Handle edge cases
4. Stability consideration: ShrinkToSharpBorder

This design isn't a silver bullet, but for Top-K scenarios, it's a very elegant trade-off choice.