2.4.3

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

有序数组的官方版本: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

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

using System;

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

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

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

        /// <summary>
        /// 返回队列是否为空。
        /// </summary>
        /// <returns></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 库查看。
无序链表

using System;

namespace PriorityQueue
{
    /// <summary>
    /// 不保持元素输入顺序的优先队列。(基于链表)
    /// </summary>
    /// <typeparam name="Key">优先队列中的元素类型。</typeparam>
    public class UnorderedLinkedMaxPQ<Key> : IMaxPQ<Key> where Key : IComparable<Key>
    {
        /// <summary>
        /// 保存元素的链表。
        /// </summary>
        private readonly LinkedList<Key> pq;

        /// <summary>
        /// 默认构造函数,建立一条优先队列。
        /// </summary>
        public UnorderedLinkedMaxPQ()
        {
            this.pq = new LinkedList<Key>();
        }

        /// <summary>
        /// 获得(但不删除)优先队列中的最大元素。
        /// </summary>
        /// <returns></returns>
        public Key Max()
        {
            int max = 0;
            for (int i = 1; i < this.pq.Size(); i++)
                if (Less(this.pq.Find(max), this.pq.Find(i)))
                    max = i;
            return this.pq.Find(max);
        }

        /// <summary>
        /// 返回并删除优先队列中的最大值。
        /// </summary>
        /// <returns></returns>
        public Key DelMax()
        {
            int max = 0;
            for (int i = 1; i < this.pq.Size(); i++)
                if (Less(this.pq.Find(max), this.pq.Find(i)))
                    max = i;

            return this.pq.Delete(max);
        }

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

        /// <summary>
        /// 检查优先队列是否为空。
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty() => this.pq.IsEmpty();

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

        /// <summary>
        /// 比较第一个元素是否小于第二个元素。
        /// </summary>
        /// <param name="a">第一个元素。</param>
        /// <param name="b">第二个元素。</param>
        /// <returns></returns>
        private bool Less(Key a, Key b) => a.CompareTo(b) < 0;
    }
}

有序链表

using System;

namespace PriorityQueue
{
    /// <summary>
    /// 元素保持输入顺序的优先队列。(基于链表)
    /// </summary>
    /// <typeparam name="Key">优先队列中的元素类型。</typeparam>
    public class OrderedLinkedMaxPQ<Key> : IMaxPQ<Key> where Key : IComparable<Key>
    {
        /// <summary>
        /// 用于保存元素的链表。
        /// </summary>
        private readonly LinkedList<Key> pq;

        /// <summary>
        /// 默认构造函数,建立一条优先队列。
        /// </summary>
        public OrderedLinkedMaxPQ()
        {
            this.pq = new LinkedList<Key>();
        }

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

        /// <summary>
        /// 返回并删除优先队列中的最大值。
        /// </summary>
        /// <returns></returns>
        public Key DelMax() => this.pq.Delete(this.pq.Size() - 1);

        /// <summary>
        /// 检查优先队列是否为空。
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty() => this.pq.IsEmpty();

        /// <summary>
        /// 获得(但不删除)优先队列中的最大元素。
        /// </summary>
        /// <returns></returns>
        public Key Max() => this.pq.Find(this.pq.Size() - 1);

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

        /// <summary>
        /// 比较第一个元素是否小于第二个元素。
        /// </summary>
        /// <param name="a">第一个元素。</param>
        /// <param name="b">第二个元素。</param>
        /// <returns></returns>
        private bool Less(Key a, Key b) => a.CompareTo(b) < 0;
    }
}

另请参阅

PriorityQueue 库

上一题 下一题