2.4.15

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

解答

MinPQ 的官方实现见:https://algs4.cs.princeton.edu/24pq/MinPQ.java.html
事实上只需要把 MaxPQ 中的比较调换方向即可。

在线性时间内检测是否是面向最小元素的堆的方法:

/// <summary>
/// 确定以 k 为根节点的二叉树是不是一个最小堆。
/// </summary>
/// <param name="k">需要检查的二叉树根节点。</param>
/// <returns></returns>
private bool IsMinHeap(int k)
{
    if (k > this.n)
        return true;
    int left = 2 * k;
    int right = 2 * k + 1;
    if (left <= this.n && Greater(k, left))
        return false;
    if (right <= this.n && Greater(k, right))
        return false;

    return IsMinHeap(left) && IsMinHeap(right);
}

用递归方法遍历整个二叉树,确认都满足堆的性质。由于每个结点都只会被比较三次(与父结点比较一次,与每个子结点各比较一次),由于 3N~N,因此这个方法是 O(n) 的。

代码

最小堆的接口 IMinPQ。

using System;

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

        /// <summary>
        /// 返回最小元素。
        /// </summary>
        /// <returns></returns>
        Key Min();

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

        /// <summary>
        /// 返回队列是否为空。
        /// </summary>
        /// <returns></returns>
        bool IsEmpty();

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

MinPQ.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace PriorityQueue
{
    /// <summary>
    /// 最小堆。(数组实现)
    /// </summary>
    /// <typeparam name="Key">最小堆中保存的元素类型。</typeparam>
    public class MinPQ<Key> : IMinPQ<Key>, IEnumerable<Key> where Key : IComparable<Key>
    {
        private Key[] pq;               // 保存元素的数组。
        private int n;                  // 堆中的元素数量。

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public MinPQ() : this(1) { }

        /// <summary>
        /// 建立指定容量的最小堆。
        /// </summary>
        /// <param name="capacity">最小堆的容量。</param>
        public MinPQ(int capacity)
        {
            this.pq = new Key[capacity + 1];
            this.n = 0;
        }

        /// <summary>
        /// 从已有元素建立一个最小堆。(O(n))
        /// </summary>
        /// <param name="keys">已有元素。</param>
        public MinPQ(Key[] keys)
        {
            this.n = keys.Length;
            this.pq = new Key[keys.Length + 1];
            for (int i = 0; i < keys.Length; i++)
                this.pq[i + 1] = keys[i];
            for (int k = this.n / 2; k >= 1; k--)
                Sink(k);
            Debug.Assert(IsMinHeap());
        }

        /// <summary>
        /// 删除并返回最小元素。
        /// </summary>
        /// <returns></returns>
        public Key DelMin()
        {
            if (IsEmpty())
                throw new ArgumentOutOfRangeException("Priority Queue Underflow");

            Key min = this.pq[1];
            Exch(1, this.n--);
            this.pq[this.n + 1] = this.pq[1];
            Sink(1);
            this.pq[this.n + 1] = default(Key);
            if ((this.n > 0) && (this.n == this.pq.Length / 4))
                Resize(this.pq.Length / 2);

            //Debug.Assert(IsMinHeap());
            return min;
        }

        /// <summary>
        /// 向堆中插入一个元素。
        /// </summary>
        /// <param name="v">需要插入的元素。</param>
        public void Insert(Key v)
        {
            if (this.n == this.pq.Length - 1)
                Resize(2 * this.pq.Length);

            this.pq[++this.n] = v;
            Swim(this.n);
            //Debug.Assert(IsMinHeap());
        }

        /// <summary>
        /// 检查堆是否为空。
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty() => this.n == 0;

        /// <summary>
        /// 获得堆中最小元素。
        /// </summary>
        /// <returns></returns>
        public Key Min() => this.pq[1];

        /// <summary>
        /// 获得堆中元素的数量。
        /// </summary>
        /// <returns></returns>
        public int Size() => this.n;

        /// <summary>
        /// 获取堆的迭代器,元素以降序排列。
        /// </summary>
        /// <returns></returns>
        public IEnumerator<Key> GetEnumerator()
        {
            MaxPQ<Key> copy = new MaxPQ<Key>(this.n);
            for (int i = 1; i <= this.n; i++)
                copy.Insert(this.pq[i]);

            while (!copy.IsEmpty())
                yield return copy.DelMax(); // 下次迭代的时候从这里继续执行。
        }

        /// <summary>
        /// 获取堆的迭代器,元素以降序排列。
        /// </summary>
        /// <returns></returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        /// <summary>
        /// 使元素上浮。
        /// </summary>
        /// <param name="k">需要上浮的元素。</param>
        private void Swim(int k)
        {
            while (k > 1 && Greater(k / 2, k))
            {
                Exch(k, k / 2);
                k /= 2;
            }
        }

        /// <summary>
        /// 使元素下沉。
        /// </summary>
        /// <param name="k">需要下沉的元素。</param>
        private void Sink(int k)
        {
            while (k * 2 <= this.n)
            {
                int j = 2 * k;
                if (Greater(j, j + 1))
                    j++;
                if (!Greater(k, j))
                    break;
                Exch(k, j);
                k = j;
            }
        }

        /// <summary>
        /// 重新调整堆的大小。
        /// </summary>
        /// <param name="capacity">调整后的堆大小。</param>
        private void Resize(int capacity)
        {
            Key[] temp = new Key[capacity];
            for (int i = 1; i <= this.n; i++)
            {
                temp[i] = this.pq[i];
            }
            this.pq = temp;
        }

        /// <summary>
        /// 判断堆中某个元素是否大于另一元素。
        /// </summary>
        /// <param name="i">判断是否较大的元素。</param>
        /// <param name="j">判断是否较小的元素。</param>
        /// <returns></returns>
        private bool Greater(int i, int j)
            => this.pq[i].CompareTo(this.pq[j]) > 0;

        /// <summary>
        /// 交换堆中的两个元素。
        /// </summary>
        /// <param name="i">要交换的第一个元素下标。</param>
        /// <param name="j">要交换的第二个元素下标。</param>
        private void Exch(int i, int j)
        {
            Key swap = this.pq[i];
            this.pq[i] = this.pq[j];
            this.pq[j] = swap;
        }

        /// <summary>
        /// 检查当前二叉树是不是一个最小堆。
        /// </summary>
        /// <returns></returns>
        private bool IsMinHeap() => IsMinHeap(1);

        /// <summary>
        /// 确定以 k 为根节点的二叉树是不是一个最小堆。
        /// </summary>
        /// <param name="k">需要检查的二叉树根节点。</param>
        /// <returns></returns>
        private bool IsMinHeap(int k)
        {
            if (k > this.n)
                return true;
            int left = 2 * k;
            int right = 2 * k + 1;
            if (left <= this.n && Greater(k, left))
                return false;
            if (right <= this.n && Greater(k, right))
                return false;

            return IsMinHeap(left) && IsMinHeap(right);
        }
    }
}

另请参阅

PriorityQueue 库

上一题 下一题