2.4.3 #

解答 #

有序数组的官方版本：https://algs4.cs.princeton.edu/24pq/OrderedArrayMaxPQ.java.html

无序数组的官方版本：https://algs4.cs.princeton.edu/24pq/UnorderedArrayMaxPQ.java.html

实现	insert()	delMax()
有序数组	N	1
有序链表	N	1
无序数组	1	N
无序链表	1	N

在库文件中定义了如下接口，所有的（最大）优先队列都会实现它。

/// <summary>
/// 实现优先队列 API 的接口。（最大堆）
/// </summary>
/// <typeparam name="TKey">优先队列容纳的元素。</typeparam>
public interface IMaxPq<TKey> where TKey : IComparable<TKey>
{
    /// <summary>
    /// 向优先队列中插入一个元素。
    /// </summary>
    /// <param name="v">插入元素的类型。</param>
    void Insert(TKey v);

    /// <summary>
    /// 返回最大元素。
    /// </summary>
    /// <returns>最大的元素。</returns>
    TKey Max();

    /// <summary>
    /// 删除并返回最大元素。
    /// </summary>
    /// <returns>最大的元素。</returns>
    TKey DelMax();

    /// <summary>
    /// 返回队列是否为空。
    /// </summary>
    /// <returns>为空则返回 <c>true</c>，否则返回 <c>false</c>。</returns>
    bool IsEmpty();

    /// <summary>
    /// 返回队列中的元素个数。
    /// </summary>
    /// <returns>队列中的元素个数。</returns>
    int Size();
}

于是我们就可以使用这样的方法测试所有类型的优先队列：

static void Test(IMaxPq<string> pq)
{
    Console.WriteLine(pq.ToString());
    pq.Insert("this");
    pq.Insert("is");
    pq.Insert("a");
    pq.Insert("test");
    while (!pq.IsEmpty())
        Console.Write(pq.DelMax() + " ");
    Console.WriteLine();
}

代码 #

给出链表的实现，基于数组的实现可以点击「另请参阅」中的 PriorityQueue 库查看。

无序链表 #

public class UnorderedLinkedMaxPq<TKey> : IMaxPq<TKey> where TKey : IComparable<TKey>
{
    /// <summary>
    /// 保存元素的链表。
    /// </summary>
    private readonly LinkedList<TKey> _pq;

    /// <summary>
    /// 默认构造函数，建立一条优先队列。
    /// </summary>
    public UnorderedLinkedMaxPq()
    {
        _pq = new LinkedList<TKey>();
    }

    /// <summary>
    /// 获得（但不删除）优先队列中的最大元素。
    /// </summary>
    /// <returns>优先队列中的最大元素。</returns>
    /// <remarks>如果希望获得并删除最大元素，请使用 <see cref="DelMax"/>。</remarks>
    public TKey Max()
    {
        var max = 0;
        for (var i = 1; i < _pq.Size(); i++)
            if (Less(_pq.Find(max), _pq.Find(i)))
                max = i;
        return _pq.Find(max);
    }

    /// <summary>
    /// 返回并删除优先队列中的最大值。
    /// </summary>
    /// <returns>优先队列中的最大元素。</returns>
    /// <remarks>如果希望获得最大元素但不删除它，请使用 <see cref="Max"/>。</remarks>
    public TKey DelMax()
    {
        var max = 0;
        for (var i = 1; i < _pq.Size(); i++)
            if (Less(_pq.Find(max), _pq.Find(i)))
                max = i;

        return _pq.Delete(max);
    }

    /// <summary>
    /// 向优先队列中插入一个元素。
    /// </summary>
    /// <param name="v">需要插入的元素。</param>
    public void Insert(TKey v) => _pq.Insert(v);

    /// <summary>
    /// 检查优先队列是否为空。
    /// </summary>
    /// <returns>如果队列为空则返回 <c>true</c>，否则返回 <c>false</c>。</returns>
    public bool IsEmpty() => _pq.IsEmpty();

    /// <summary>
    /// 检查优先队列中含有的元素数量。
    /// </summary>
    /// <returns>优先队列中含有元素的数量。</returns>
    public int Size() => _pq.Size();

    /// <summary>
    /// 比较第一个元素是否小于第二个元素。
    /// </summary>
    /// <param name="a">第一个元素。</param>
    /// <param name="b">第二个元素。</param>
    /// <returns>如果 <paramref name="a"/> 较小则返回 <c>true</c>，否则返回 <c>false</c>。</returns>
    private bool Less(TKey a, TKey b) => a.CompareTo(b) < 0;
}

有序链表

public class OrderedLinkedMaxPq<TKey> : IMaxPq<TKey> where TKey : IComparable<TKey>
{
    /// <summary>
    /// 用于保存元素的链表。
    /// </summary>
    private readonly LinkedList<TKey> _pq;

    /// <summary>
    /// 默认构造函数，建立一条优先队列。
    /// </summary>
    public OrderedLinkedMaxPq()
    {
        _pq = new LinkedList<TKey>();
    }

    /// <summary>
    /// 向优先队列中插入一个元素。
    /// </summary>
    /// <param name="v">需要插入的元素。</param>
    public void Insert(TKey v)
    {
        var i = _pq.Size() - 1;
        while (i >= 0 && Less(v, _pq.Find(i)))
            i--;
        _pq.Insert(v, i + 1);
    }

    /// <summary>
    /// 返回并删除优先队列中的最大值。
    /// </summary>
    /// <returns>优先队列中的最大值。</returns>
    /// <remarks>如果希望获得最大值而不删除它，请使用 <see cref="Max"/>。</remarks>
    public TKey DelMax() => _pq.Delete(_pq.Size() - 1);

    /// <summary>
    /// 检查优先队列是否为空。
    /// </summary>
    /// <returns>如果为空则返回 <c>true</c>，否则返回 <c>false</c>。</returns>
    public bool IsEmpty() => _pq.IsEmpty();

    /// <summary>
    /// 获得（但不删除）优先队列中的最大元素。
    /// </summary>
    /// <returns>优先队列中的最大元素。</returns>
    /// <remarks>如果希望获得并删除最大元素，请使用 <see cref="DelMax"/>。</remarks>
    public TKey Max() => _pq.Find(_pq.Size() - 1);

    /// <summary>
    /// 检查优先队列中含有的元素数量。
    /// </summary>
    /// <returns>优先队列中的元素数量。</returns>
    public int Size() => _pq.Size();

    /// <summary>
    /// 比较第一个元素是否小于第二个元素。
    /// </summary>
    /// <param name="a">第一个元素。</param>
    /// <param name="b">第二个元素。</param>
    /// <returns>如果 <paramref name="a"/> 较小则返回 <c>true</c>，否则返回 <c>false</c>。</returns>
    private bool Less(TKey a, TKey b) => a.CompareTo(b) < 0;
}

另请参阅 #

PriorityQueue 库