基于堆实现优先队列：是否应采用继承方式？

我正在自定义实现AStar算法，需要实现优先队列，因此得先实现堆结构。目前对自己的堆实现比较满意，但纠结优先队列的实现方式——当前两种方案都能运行，但担心后续出问题。

方案一：组合式实现 #

抽象类代码：

public abstract class PriorityQueueAbstract<T, TPriority>
{
    HeapAbstract<Tuple<T, TPriority>> heap;
    protected PriorityQueueAbstract(HeapAbstract<Tuple<T, TPriority>> heapImplementation) => heap = heapImplementation;
    public void Enqueue(T item, TPriority priority) => heap.Insert(new Tuple<T, TPriority>(item, priority));
    public T Dequeue() => heap.Extract().Item1;
}

具体实现类：

public class MinPriorityQueue<T, TPriority> : PriorityQueueAbstract<T, TPriority> where TPriority : IComparable
{
    public MinPriorityQueue() : base(new Heap<Tuple<T, TPriority>>(new T2Comparer<T, TPriority>())) { }
}

堆支持传入Comparer参数，这里用了元组比较器T2Comparer（名称需要优化建议），要求TPriority实现IComparable。

方案二：继承式实现 #

抽象类代码：

public abstract class PriorityQueueAbstract<T, TPriority> : HeapAbstract<Tuple<T, TPriority>>
{
    public void Enqueue(T item, TPriority priority) => Insert(new Tuple<T, TPriority>(item, priority));
    public T Dequeue() => Extract().Item1;
}

具体实现类：

public class MinPriorityQueue<T, TPriority> : PriorityQueueAbstract<T, TPriority> where TPriority : IComparable
{
    protected override int Compare(Tuple<T, TPriority> firstItem, Tuple<T, TPriority> secondItem)
    {
        return firstItem.Item2.CompareTo(secondItem.Item2);
    }
}

第二种方案需要重写堆要求的Compare方法，优点是清晰易扩展，但问题是直接继承堆后，用户除了Enqueue/Dequeue，还能调用堆的Insert/Extract方法，隐藏这些方法的方式不够优雅。

额外说明：无法使用最新版.NET。

疑问 #

• 该如何选择两种方案？
• 相关最佳实践是什么？
• 是否有更优的实现方式？

两种方案核心对比 #

方案一（组合式）：遵循「组合优于继承」原则 #

• 优点：
  • 完全封装堆的内部实现，对外只暴露优先队列的核心操作Enqueue/Dequeue，避免用户误用堆的底层方法，符合接口隔离原则。
  • 堆的实现和优先队列解耦，后续堆的修改不会直接影响优先队列，扩展性更强。
• 缺点：
  • 需要额外实现比较器类，代码量稍多。

方案二（继承式）：耦合度高，风险大 #

• 优点：
  • 代码结构直观，无需额外比较器，直接重写Compare方法即可完成优先级逻辑。
• 缺点：
  • 违反「组合优于继承」的设计原则，优先队列和堆的职责边界模糊。用户可以直接调用堆的Insert/Extract，破坏优先队列的抽象封装，容易引发逻辑错误（比如直接插入未封装优先级的元组）。
  • 若后续堆的接口变更，优先队列必须同步修改，维护成本高。

最佳实践选择 #

优先选择方案一（组合式实现），原因如下：

1. 符合面向对象设计的核心原则：组合优于继承，降低模块间耦合。
2. 严格封装内部细节，对外提供清晰的优先队列接口，避免误用。
3. 更灵活：如果后续需要更换堆的实现（比如换成更高效的结构），只需要修改具体优先队列类的构造函数，无需改动上层调用代码。

优化建议 #

1. 比较器命名优化 #

T2Comparer可以更语义化，比如：

• TupleSecondItemComparer<T, TPriority>：明确表示比较元组的第二个元素
• PriorityBasedComparer<T, TPriority>：突出是基于优先级的比较

实现示例：

public class PriorityBasedComparer<T, TPriority> : IComparer<Tuple<T, TPriority>> where TPriority : IComparable
{
    public int Compare(Tuple<T, TPriority> x, Tuple<T, TPriority> y)
    {
        if (x == null || y == null) throw new ArgumentNullException();
        return x.Item2.CompareTo(y.Item2);
    }
}

2. 更优的实现方式：依赖抽象堆接口 #

可以进一步优化方案一，让优先队列依赖抽象的堆接口而非具体实现，提升灵活性：

// 定义堆的接口
public interface IHeap<T>
{
    void Insert(T item);
    T Extract();
    bool IsEmpty { get; }
}

// 优先队列抽象类依赖接口
public abstract class PriorityQueueAbstract<T, TPriority>
{
    protected readonly IHeap<Tuple<T, TPriority>> _heap;

    protected PriorityQueueAbstract(IHeap<Tuple<T, TPriority>> heap)
    {
        _heap = heap ?? throw new ArgumentNullException(nameof(heap));
    }

    public void Enqueue(T item, TPriority priority)
    {
        _heap.Insert(Tuple.Create(item, priority));
    }

    public T Dequeue()
    {
        if (_heap.IsEmpty) throw new InvalidOperationException("Queue is empty");
        return _heap.Extract().Item1;
    }

    public bool IsEmpty => _heap.IsEmpty;
}

// 最小优先队列实现
public class MinPriorityQueue<T, TPriority> : PriorityQueueAbstract<T, TPriority> where TPriority : IComparable
{
    public MinPriorityQueue() : base(new Heap<Tuple<T, TPriority>>(new PriorityBasedComparer<T, TPriority>()))
    {
    }
}

这种方式的好处是：

• 依赖倒置：优先队列依赖抽象的IHeap接口，后续可以轻松替换堆的实现（比如测试时用模拟堆）。
• 增加IsEmpty等实用方法，完善优先队列的接口。

3. 替换Tuple为语义化类 #

如果觉得Tuple<T, TPriority>不够直观，可以自定义PriorityItem类提升可读性：

public class PriorityItem<T, TPriority>
{
    public T Item { get; }
    public TPriority Priority { get; }

    public PriorityItem(T item, TPriority priority)
    {
        Item = item;
        Priority = priority;
    }
}

// 对应的比较器
public class PriorityItemComparer<T, TPriority> : IComparer<PriorityItem<T, TPriority>> where TPriority : IComparable
{
    public int Compare(PriorityItem<T, TPriority> x, PriorityItem<T, TPriority> y)
    {
        if (x == null || y == null) throw new ArgumentNullException();
        return x.Priority.CompareTo(y.Priority);
    }
}

// 调整优先队列使用PriorityItem
public abstract class PriorityQueueAbstract<T, TPriority>
{
    protected readonly IHeap<PriorityItem<T, TPriority>> _heap;

    protected PriorityQueueAbstract(IHeap<PriorityItem<T, TPriority>> heap)
    {
        _heap = heap ?? throw new ArgumentNullException(nameof(heap));
    }

    public void Enqueue(T item, TPriority priority)
    {
        _heap.Insert(new PriorityItem<T, TPriority>(item, priority));
    }

    public T Dequeue()
    {
        if (_heap.IsEmpty) throw new InvalidOperationException("Queue is empty");
        return _heap.Extract().Item;
    }

    public bool IsEmpty => _heap.IsEmpty;
}

这样代码可读性会大幅提升，避免Item1/Item2这类模糊命名。

内容的提问来源于stack exchange，提问作者Kwenchin