C# 實作帶鍵值優先佇列：支援 O(log n) 更新鍵值

標準優先佇列 (PriorityQueue<T>) 不支援高效更新元素優先級。本文實作 KeyedPriorityQueue<T, K, V>：內部以**二元堆** + **Dictionary<K, int> 索引** 實現，支援 Push、Pop、Update (依鍵值修改優先級/值) 全部 O(log n)，適用於 Dijkstra/A* 演算法、任務排程器、快取淘汰等場景。

核心資料結構

• T[] _heap：二元最大堆 (根節點優先級最高)
• Dictionary<K, int> _index：鍵 K → 堆陣列索引，支援 O(1) 定位
• IComparer<T> _comparer：元素比較策略
• IKeyValue<T, K, V> _kv：從元素提取鍵/值、設定值的介面

介面定義

public interface IKeyValue
{
    K GetKey(T item);
    V GetValue(T item);
    void SetValue(T item, V value);
}

完整實作

using System;
using System.Collections.Generic;

public class KeyedPriorityQueue
{
    private readonly IComparer _comparer;
    private readonly IKeyValue _kv;
    private readonly Dictionary _index;
    private T[] _heap;
    public int Count { get; private set; }

    public KeyedPriorityQueue(IKeyValue kv) : this(null, kv) { }
    public KeyedPriorityQueue(int capacity, IKeyValue kv) : this(capacity, null, kv) { }
    public KeyedPriorityQueue(IComparer comparer, IKeyValue kv) : this(16, comparer, kv) { }

    public KeyedPriorityQueue(int capacity, IComparer comparer, IKeyValue kv)
    {
        _comparer = comparer ?? Comparer.Default;
        _kv = kv;
        _index = new Dictionary();
        _heap = new T[capacity];
    }

    public bool ContainsKey(K key) => _index.ContainsKey(key);

    /// 

    /// 更新元素值並調整堆位置 (O(log n))
    /// 
    public void Update(T item)
    {
        if (_kv == null) throw new NotSupportedException("需提供 IKeyValue 實作");
        if (typeof(T).IsValueType) throw new InvalidOperationException("T 必須為參考型別以支援 Update");

        K key = _kv.GetKey(item);
        if (!_index.TryGetValue(key, out int pos)) throw new KeyNotFoundException($"鍵 {key} 不存在");

        T old = _heap[pos];
        int cmp = _comparer.Compare(item, old);
        _kv.SetValue(old, _kv.GetValue(item)); // 更新值 (參考型別直接修改物件內容)

        if (cmp < 0) SiftDown(pos);
        else if (cmp > 0) SiftUp(pos);
        // cmp == 0 無需調整
    }

    public void Push(T item)
    {
        if (Count >= _heap.Length) Array.Resize(ref _heap, Count * 2);
        if (_kv != null) _index[_kv.GetKey(item)] = Count;
        _heap[Count] = item;
        SiftUp(Count++);
    }

    public T Pop()
    {
        T top = _heap[0];
        if (_kv != null) _index.Remove(_kv.GetKey(top));
        _heap[0] = _heap[--Count];
        if (Count > 0) SiftDown(_kv != null ? (_index[_kv.GetKey(_heap[0])] = 0) : 0);
        return top;
    }

    public T Peek() => Count > 0 ? _heap[0] : throw new InvalidOperationException("佇列為空");

    private void SiftUp(int n)
    {
        T item = _heap[n];
        while (n > 0)
        {
            int parent = (n - 1) / 2;
            if (_comparer.Compare(item, _heap[parent]) <= 0) break;
            _heap[n] = _heap[parent];
            if (_kv != null) _index[_kv.GetKey(_heap[parent])] = n;
            n = parent;
        }
        _heap[n] = item;
        if (_kv != null) _index[_kv.GetKey(item)] = n;
    }

    private void SiftDown(int n)
    {
        T item = _heap[n];
        while (true)
        {
            int left = 2 * n + 1;
            if (left >= Count) break;
            int right = left + 1;
            int largest = (right < Count && _comparer.Compare(_heap[right], _heap[left]) > 0) ? right : left;
            if (_comparer.Compare(item, _heap[largest]) >= 0) break;
            _heap[n] = _heap[largest];
            if (_kv != null) _index[_kv.GetKey(_heap[largest])] = n;
            n = largest;
        }
        _heap[n] = item;
        if (_kv != null) _index[_kv.GetKey(item)] = n;
    }
}

使用範例：Dijkstra 最短路徑

public class Node
{
    public int Id { get; set; }
    public int Dist { get; set; } = int.MaxValue;
}

public class NodeKeyValue : IKeyValue
{
    public int GetKey(Node n) => n.Id;
    public int GetValue(Node n) => n.Dist;
    public void SetValue(Node n, int v) => n.Dist = v;
}

var pq = new KeyedPriorityQueue(new NodeKeyValue());
var nodes = Enumerable.Range(1, 5).Select(i => new Node { Id = i }).ToList();
nodes[0].Dist = 0; // 起點
foreach (var n in nodes) pq.Push(n);

while (pq.Count > 0)
{
    var u = pq.Pop();
    Console.WriteLine($"處理節點 {u.Id}, 距離 {u.Dist}");
    // Relax 鄰邊...
    // 更新鄰居距離
    var v = nodes[1];
    if (v.Dist > u.Dist + 10)
    {
        v.Dist = u.Dist + 10;
        pq.Update(v); // O(log n) 更新優先級
    }
}

衍生簡易 PriorityQueue<T> (無鍵值版)

public class PriorityQueue : KeyedPriorityQueue
{
    public PriorityQueue() : base(null) { }
    public PriorityQueue(int capacity) : base(capacity, null) { }
    public PriorityQueue(IComparer comparer) : base(comparer, null) { }
    public PriorityQueue(int capacity, IComparer comparer) : base(capacity, comparer, null) { }
}

效能基準 (參考)

.NET 6 內建 PriorityQueue<TElement, TPriority> 效能極佳但缺乏更新功能。若需頻繁更新優先級 (如 Dijkstra、A*、動態任務排程)，本實作為最佳選擇。