Priority Queue ใน C#

Priority Queue คือโครงสร้างข้อมูลที่จัดเก็บ Element พร้อม Priority — Element ที่มี Priority สูงสุด (หรือต่ำสุด) จะถูก Dequeue ก่อน

.NET 6+: PriorityQueue<TElement, TPriority> (Built-in)

ตั้งแต่ .NET 6 มี Implementation อยู่ใน System.Collections.Generic

การใช้งานพื้นฐาน

using System.Collections.Generic;

var pq = new PriorityQueue();

// Enqueue: (Element, Priority) — Priority ต่ำ = สูงสุด (Min-Heap)
pq.Enqueue("Low Priority Task", 3);
pq.Enqueue("High Priority Task", 1);
pq.Enqueue("Medium Priority Task", 2);

Console.WriteLine($"Count: {pq.Count}"); // 3

// Dequeue: ดึง Element ที่ Priority ต่ำสุด
while (pq.Count > 0) {
    string task = pq.Dequeue();
    Console.WriteLine($"Processing: {task}");
}
// Output:
// Processing: High Priority Task
// Processing: Medium Priority Task
// Processing: Low Priority Task

ตัวเลือก: Max-Heap (Priority สูง = Dequeue ก่อน)

// ใช้ Comparer.Reverse หรือ Priority เป็นค่าลบ
var maxPq = new PriorityQueue(Comparer.Create((a, b) => b.CompareTo(a)));
maxPq.Enqueue("Low", 1);
maxPq.Enqueue("High", 10);
maxPq.Dequeue(); // "High" (Priority 10 สูงสุด)

Custom Implementation (ก่อน .NET 6 / เพื่อการศึกษา)

public class MyPriorityQueue where T : IComparable {
    private List _items = new List();
    
    public int Count => _items.Count;
    
    public void Enqueue(T item) {
        _items.Add(item);
        HeapifyUp(_items.Count - 1);
    }
    
    public T Dequeue() {
        if (_items.Count == 0) throw new InvalidOperationException("Queue empty");
        T root = _items[0];
        _items[0] = _items[_items.Count - 1];
        _items.RemoveAt(_items.Count - 1);
        HeapifyDown(0);
        return root;
    }
    
    private void HeapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (_items[index].CompareTo(_items[parent]) >= 0) break;
            Swap(index, parent);
            index = parent;
        }
    }
    
    private void HeapifyDown(int index) {
        while (true) {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int smallest = index;
            
            if (left < _items.Count && _items[left].CompareTo(_items[smallest]) < 0)
                smallest = left;
            if (right < _items.Count && _items[right].CompareTo(_items[smallest]) < 0)
                smallest = right;
            if (smallest == index) break;
            
            Swap(index, smallest);
            index = smallest;
        }
    }
    
    private void Swap(int i, int j) {
        (_items[i], _items[j]) = (_items[j], _items[i]);
    }
}

การประยุกต์ใช้

• Task Scheduling (OS, Thread Pool)
• Dijkstra / A* Pathfinding
• Huffman Coding
• Event Simulation (Time-based)
• Load Balancing (Least Connections)

Complexity

สรุป

• .NET 6+: ใช้ PriorityQueue<TElement, TPriority> Built-in — เร็ว ทดสอบแล้ว Thread-Unsafe
• Multi-threaded: ต้อง Lock เอง หรือใช้ ConcurrentPriorityQueue (Third-party)
• Priority ต่ำ = Dequeue ก่อน (Min-Heap) — ใช้ Comparer<T>.Create เพื่อกลับลำดับ