1. 全栈程序员必看首页

优先队列「建议收藏」

全栈程序员-站长 • • 未分类 • 阅读 26

优先队列「建议收藏」优先队列比如现实生活中的排队，就符合这种先进先出的队列形式，但是像急诊医院排队，就不可能按照先到先治疗的规则，所以需要使用优先队列。实现优先队列其实都是基于下面这些实现的：可以看出来实现优先队列最

大家好，又见面了，我是你们的朋友全栈君。

优先队列  

比如现实生活中的排队，就符合这种先进先出的队列形式，但是像急诊医院排队，就不可能按照先到先治疗的规则，所以需要使用优先队列。

实现优先队列其实都是基于下面这些实现的：可以看出来实现优先队列最好的方式就是二叉堆。

优先队列「建议收藏」

 

 

 （1）二叉堆本质上是一种完全二叉树 

比如下面2棵树，左边的树是完全二叉树，右边不是，因为没有连续集中在左侧。定义1的意思是指

优先队列「建议收藏」

二叉堆的定义：

优先队列「建议收藏」

 

用数组来存储堆：如下图，父节点左孩子节点是本身索引的2倍，右孩子节点的索引是本身节点的2倍+1，这样只要知道其中一个节点的信息，就能迅速知道父节点或对应孩子节点的信息了。

优先队列「建议收藏」

 

最大堆

二叉堆分为2个类型，最大堆和最小堆，对于最大堆：最大堆任何一个父节点的值，都大于等于它左右孩子节点的值。

所以在插入新值68的时候，首先要满足作为完全二叉树的条件，就是最下层节点必须连续集中在左侧，所以放在11的位置，如下图：

优先队列「建议收藏」

如果这个二叉堆是最大堆，那么需要元素上游，和对应父节点进行比较，结果如下图：

优先队列「建议收藏」

如果我们要删除其中一个元素，比如根节点70，那我们需要将70和最下层的最右边的一个节点进行交换，然后删除70，如下：

 

优先队列「建议收藏」

 

但是此时明显不符合最大堆的定义，所以进行元素下沉：55和65都比28要大，但是我们选择和65交换，因为要满足最大堆的定义，这是风险最小的选择。

优先队列「建议收藏」

 

 

 

 代码实现:

namespace DataStructure
{
    /// <summary>
    /// 数组堆
    /// </summary>
    /// <typeparam name="E"></typeparam>
    class MaxHeap<E> where E : IComparable<E>
    {

        private E[] heap;
        private int N;
        public MaxHeap(int capacity)
        {
            //之所以加1，是因为索引为0的地方是没有存值的。
            heap = new E[capacity + 1];
        }

        public MaxHeap() : this(10)
        {

        }

        public int Count { get { return N; } }
        public bool IsEmpty { get { return N == 0; } }

        public void Insert(E e)
        {
            //之所以减一，是因为二叉堆中的具体数是在索引1处开始。
            if (N == heap.Length - 1)
            {
                ResetCapacity(heap.Length * 2);
            }

            //首先保证此树是完全二叉树。
            heap[N + 1] = e;
            N++;
            Swim(N);
        }
        /// <summary>
        /// 元素上游
        /// </summary>
        /// <param name="k"></param>
        private void Swim(int k)
        {
            //k==1时代表找到了根节点，所以不用再比较了，不能上游了
            while (k > 1 && heap[k].CompareTo(heap[k / 2]) > 0)
            {
                Swap(k, k / 2);
                k = k / 2;
            }

        }

        private void Swap(int i, int j)
        {
            E e = heap[i];
            heap[i] = heap[j];
            heap[j] = e;
        }
        //删除最大元素
        public E RemoveMax()
        {
            if (IsEmpty)
                throw new Exception("堆为空");
            Swap(1, N);
            E max = heap[N];
            //设置默认值，让垃圾回收器GC进行回收。
            heap[N] = default;
            N--;
            Sink(1);
            if (N == (heap.Length - 1) / 4)
                ResetCapacity(heap.Length / 2);
            return max;
        }
        /// <summary>
        ///返回最大值
        /// </summary>
        /// <returns></returns>
        public E Max()
        {
            if (IsEmpty)
                throw new Exception("堆为空");
            return heap[1];
        }

        /// <summary>
        /// 元素下沉
        /// </summary>
        /// <param name="k"></param>
        private void Sink(int k)
        {
            //当前存在孩子节点的时候才能往下比较
            while (2 * k <= N)
            {
                int j = 2 * k;
                //j+1<=N表示存在右孩子节点，
                //如果存在右孩子节点，并且右孩子节点比左孩子节点大
                if (j + 1 <= N && heap[j + 1].CompareTo(heap[j]) > 0)
                {
                    //右孩子的位置
                    j++;
                }
                //如果当前节点大于右孩子节点，则跳出
                if (heap[k].CompareTo(heap[j]) >= 0)
                {
                    break;
                }

                Swap(k, j);
                //j代表交换完成之后元素所在的新的位置，赋给k，看看这个位置是否需要继续交换
                k = j;
            }

        }

        /// <summary>
        /// 数组扩容
        /// </summary>
        /// <param name="newLength"></param>
        private void ResetCapacity(int newLength)
        {
            E[] newData = new E[newLength];
            //将旧有数据复制到扩容后的新数组中
            heap.CopyTo(newData, 0);
            //赋值给原有数组 注意此时给data的是引用，data中数据更改newData同样会变
            heap = newData;
        }
        /// <summary>
        /// 重写输出方法
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.Append("[");
            for (int i = 1; i <=N; i++)
            {
                stringBuilder.Append(heap[i]);
                if (i != N)
                    stringBuilder.Append(",");
            }
            stringBuilder.Append("]");
            return stringBuilder.ToString();
        }




    }
}

 

 调用：

按照二叉堆最大堆的定义，实现结果应为：

优先队列「建议收藏」

  class Program
    {
        static void Main(string[] args)
        {  
            MaxHeap<int> maxHeap = new MaxHeap<int>(); 
            int[] arr = { 3,2,1,5,4};  
            for (int i = 0; i < arr.Length; i++)
            {
                maxHeap.Insert(arr[i]);
                Console.WriteLine(maxHeap);
            }

            maxHeap.RemoveMax(); 
            Console.WriteLine(maxHeap);

        }
    }

 

结果：

[3]
[3,2]
[3,2,1]
[5,3,1,2]
[5,4,1,2,3]
[4,3,1,2]

 和预期一致。

 

最小堆

 最小堆任何一个父节点的值，都小于等于它左右孩子节点的值。

 

堆排序

 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了（一般升序采用大顶堆，降序采用小顶堆)。

代码如下：

    class HeapSort1
    {
        public static void Sort(int[] arr)
        {
            int n = arr.Length;
            MaxHeap<int> maxHeap = new MaxHeap<int>(n);
            for (int i = 0; i < n; i++)
            {
                maxHeap.Insert(arr[i]);
            }
            //要想实现正序，那么最大值就是放后面，所以i--；
            for (int i = n - 1; i >= 0; i--)
            {
                arr[i] = maxHeap.RemoveMax();
            }  
        } 
    }

 

但是，当前代码的性能不是很好，他的时间复杂度：建堆(nlogn)+出堆(nlogn)=O(2nlogn)，空间复杂度为O(n)

可以使用原地堆排序进行优化。

原地堆排序

如下图，符合完全二叉树，但是不符合最大堆定义。 图中的橙色节点都是叶子节点，我们可以从第一个非叶子节点开始进行考察，其中n代表数组的个数。

 优先队列「建议收藏」

 

 

class HeapSort2
    {
        public static void Sort(int[] arr)
        {
            int n = arr.Length;
            MaxHeap<int> maxHeap = new MaxHeap<int>(n);
            for (int i = 0; i < n; i++)
            {
                maxHeap.Insert(arr[i]);
            }
            //因为要从第一个非叶子节点开始，并且期间需要元素下沉来实现最大堆。
            for (int i = (n - 1 - 1) / 2; i >= 0; i--)
            {
                Sink(arr, i, n - 1);
            }
            //原地堆排序
            for (int i = n - 1; i >= 0; i--)
            {
                //交换元素
                Swap(arr, 0, i); 
                //交换之后再次比较
                Sink(arr, 0, i - 1); 
            } 
        }

        /// <summary>
        /// 元素下沉
        /// </summary>
        /// <param name="k"></param>
        private static void Sink(int[] arr, int k, int N)
        {
            //当前存在孩子节点的时候才能往下比较
            while (2 * k + 1 <= N)
            {
                int j = 2 * k + 1;
                //j+1<=N表示存在右孩子节点，
                //如果存在右孩子节点，并且右孩子节点比左孩子节点大
                if (j + 1 <= N && arr[j + 1].CompareTo(arr[j]) > 0)
                {
                    //右孩子的位置
                    j++;
                }
                //如果当前节点大于右孩子节点，则跳出
                if (arr[k].CompareTo(arr[j]) >= 0)
                {
                    break;
                }

                Swap(arr, k, j);
                //j代表交换完成之后元素所在的新的位置，赋给k，看看这个位置是否需要继续交换
                k = j;
            }

        }
        private static void Swap(int[] arr, int i, int j)
        {
            int e = arr[i];
            arr[i] = arr[j];
            arr[j] = e;
        }


    }

 

 

优先队列

基于最大堆实现最大优先队列

完整代码：

最大最小数组堆：

namespace DataStructure
{
    /// <summary>
    /// 最大数组堆
    /// </summary>
    /// <typeparam name="E"></typeparam>
    class MaxHeap<E> where E : IComparable<E>
    {

        private E[] heap;
        private int N;
        public MaxHeap(int capacity)
        {
            //之所以加1，是因为索引为0的地方是没有存值的。
            heap = new E[capacity + 1];
            N = 0;
        }

        public MaxHeap() : this(10)
        {
        }
        public int Count { get { return N; } }
        public bool IsEmpty { get { return N == 0; } }

        public void Insert(E e)
        {
            //之所以减一，是因为二叉堆中的具体数是在索引1处开始。
            if (N == heap.Length - 1)
            {
                ResetCapacity(heap.Length * 2);
            }

            //首先保证此树是完全二叉树。
            heap[N + 1] = e;
            N++;
            Swim(N);
        }
        /// <summary>
        /// 元素上游
        /// </summary>
        /// <param name="k"></param>
        private void Swim(int k)
        {
            //k==1时代表找到了根节点，所以不用再比较了，不能上游了
            while (k > 1 && heap[k].CompareTo(heap[k / 2]) > 0)
            {
                Swap(k, k / 2);
                k = k / 2;
            }

        }

        private void Swap(int i, int j)
        {
            E e = heap[i];
            heap[i] = heap[j];
            heap[j] = e;
        }
        //删除最大元素
        public E RemoveMax()
        {
            if (IsEmpty)
                throw new Exception("堆为空");
            Swap(1, N);
            E max = heap[N];
            //设置默认值，让垃圾回收器GC进行回收。
            heap[N] = default;
            N--;
            Sink(1);
            if (N == (heap.Length - 1) / 4)
                ResetCapacity(heap.Length / 2);
            return max;
        }
        /// <summary>
        ///返回最大值
        /// </summary>
        /// <returns></returns>
        public E Max()
        {
            if (IsEmpty)
                throw new Exception("堆为空");
            return heap[1];
        }

        /// <summary>
        /// 元素下沉
        /// </summary>
        /// <param name="k"></param>
        private void Sink(int k)
        {
            //当前存在孩子节点的时候才能往下比较
            while (2 * k <= N)
            {
                int j = 2 * k;
                //j+1<=N表示存在右孩子节点，
                //如果存在右孩子节点，并且右孩子节点比左孩子节点大
                if (j + 1 <= N && heap[j + 1].CompareTo(heap[j]) > 0)
                {
                    //右孩子的位置
                    j++;
                }
                //如果当前节点大于右孩子节点，则跳出
                if (heap[k].CompareTo(heap[j]) >= 0)
                {
                    break;
                }

                Swap(k, j);
                //j代表交换完成之后元素所在的新的位置，赋给k，看看这个位置是否需要继续交换
                k = j;
            }

        }

        /// <summary>
        /// 数组扩容
        /// </summary>
        /// <param name="newLength"></param>
        private void ResetCapacity(int newLength)
        {
            E[] newData = new E[newLength];
            //将旧有数据复制到扩容后的新数组中
            heap.CopyTo(newData, 0);
            //赋值给原有数组 注意此时给data的是引用，data中数据更改newData同样会变
            heap = newData;
        }
        /// <summary>
        /// 重写输出方法
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.Append("[");
            for (int i = 1; i <= N; i++)
            {
                stringBuilder.Append(heap[i]);
                if (i != N)
                    stringBuilder.Append(",");
            }
            stringBuilder.Append("]");
            return stringBuilder.ToString();
        }




    }
     
    /// <summary>
    /// 最小数组堆
    /// </summary>
    /// <typeparam name="E"></typeparam>
    class MinHeap<E> where E : IComparable<E>
    {

        private E[] heap;
        private int N;
        public MinHeap(int capacity)
        {
            //之所以加1，是因为索引为0的地方是没有存值的。
            heap = new E[capacity + 1];
            N = 0;
        }

        public MinHeap() : this(10)
        {
        }
        public int Count { get { return N; } }
        public bool IsEmpty { get { return N == 0; } }

        public void Insert(E e)
        {
            //之所以减一，是因为二叉堆中的具体数是在索引1处开始。
            if (N == heap.Length - 1)
            {
                ResetCapacity(heap.Length * 2);
            }

            //首先保证此树是完全二叉树。
            heap[N + 1] = e;
            N++;
            Swim(N);
        }
        /// <summary>
        /// 元素上游
        /// </summary>
        /// <param name="k"></param>
        private void Swim(int k)
        {
            //k==1时代表找到了根节点，所以不用再比较了，不能上游了
            while (k > 1 && heap[k].CompareTo(heap[k / 2]) < 0)
            {
                Swap(k, k / 2);
                k = k / 2;
            }

        }

        private void Swap(int i, int j)
        {
            E e = heap[i];
            heap[i] = heap[j];
            heap[j] = e;
        }
        //删除最小元素
        public E RemoveMin()
        {
            if (IsEmpty)
                throw new Exception("堆为空");
            Swap(1, N);
            E max = heap[N];
            //设置默认值，让垃圾回收器GC进行回收。
            heap[N] = default;
            N--;
            Sink(1);
            if (N == (heap.Length - 1) / 4)
                ResetCapacity(heap.Length / 2);
            return max;
        }
        /// <summary>
        ///返回最小值
        /// </summary>
        /// <returns></returns>
        public E Min()
        {
            if (IsEmpty)
                throw new Exception("堆为空");
            return heap[1];
        }

        /// <summary>
        /// 元素下沉
        /// </summary>
        /// <param name="k"></param>
        private void Sink(int k)
        {
            //当前存在孩子节点的时候才能往下比较
            while (2 * k <= N)
            {
                int j = 2 * k;
                //j+1<=N表示存在右孩子节点，
                //如果存在右孩子节点，并且右孩子节点比左孩子节点小
                if (j + 1 <= N && heap[j + 1].CompareTo(heap[j]) < 0)
                {
                    //右孩子的位置
                    j++;
                }
                //如果当前节点小于右孩子节点，则跳出
                if (heap[k].CompareTo(heap[j]) <= 0)
                {
                    break;
                }

                Swap(k, j);
                //j代表交换完成之后元素所在的新的位置，赋给k，看看这个位置是否需要继续交换
                k = j;
            }

        }

        /// <summary>
        /// 数组扩容
        /// </summary>
        /// <param name="newLength"></param>
        private void ResetCapacity(int newLength)
        {
            E[] newData = new E[newLength];
            //将旧有数据复制到扩容后的新数组中
            heap.CopyTo(newData, 0);
            //赋值给原有数组 注意此时给data的是引用，data中数据更改newData同样会变
            heap = newData;
        }
        /// <summary>
        /// 重写输出方法
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.Append("[");
            for (int i = 1; i <= N; i++)
            {
                stringBuilder.Append(heap[i]);
                if (i != N)
                    stringBuilder.Append(",");
            }
            stringBuilder.Append("]");
            return stringBuilder.ToString();
        }
 
    }
}

 

最大最小优先队列：

namespace DataStructure
{
    /// <summary>
    /// 最大优先队列  IQueue：是自定义的一个接口
    /// </summary>
    /// <typeparam name="E"></typeparam>
    class MaxPQ<E> : IQueue<E> where E : IComparable<E>
    {
        private MaxHeap<E> heap;

        public int Count { get { return heap.Count; } }

        public bool IsEmpty { get { return heap.IsEmpty; } }

        public MaxPQ(int capacity)
        {
            heap = new MaxHeap<E>(capacity);
        }
        public MaxPQ()
        {
            heap = new MaxHeap<E>();
        }

        public void Enqueue(E e)
        {
            heap.Insert(e);
        }

        public E Dequeue()
        {
            return heap.RemoveMax();
        }

        public E Peek()
        {
            return heap.Max();
        }
    }

    /// <summary>
    /// 最小优先队列  
    /// </summary>
    /// <typeparam name="E"></typeparam>
    class MinPQ<E> : IQueue<E> where E : IComparable<E>
    {
        private MinHeap<E> heap;

        public int Count { get { return heap.Count; } }

        public bool IsEmpty { get { return heap.IsEmpty; } }

        public MinPQ(int capacity)
        {
            heap = new MinHeap<E>(capacity);
        }
        public MinPQ()
        {
            heap = new MinHeap<E>();
        }

        public void Enqueue(E e)
        {
            heap.Insert(e);
        }

        public E Dequeue()
        {
            return heap.RemoveMin();
        }

        public E Peek()
        {
            return heap.Min();
        }
    }
}

 

 

 

（1）在一百万个元素中找出前10个最小的元素。

最好用优先队列，因为其他那些排序方法需要把1百万个数据先放到内存中才能进行排序，通过优先队列，来一个数据，就处理一个，不需要那么多的内存，只需要开辟10个内存来储存即可。

我们可以把数据规模缩小来进行测试，如下：

优先队列「建议收藏」

 

我们可以先找出3个元素，然后将剩余的元素和选出来的元素进行比较，如果存在比这3个元素小的，则替换，否则继续比较。

   class Program
    {

        static void Main(string[] args)
        {
            //找最小的三个数
            MaxPQ<int> maxHeap = new MaxPQ<int>(3);
            int[] arr = { 3, 2, 1, 5, 4 };
            for (int i = 0; i < arr.Length; i++)
            {
                if (maxHeap.Count < 3)
                {
                    maxHeap.Enqueue(arr[i]);
                }
                //如果当前数比最大数还小，则去除最大数，
                else if (arr[i] < maxHeap.Peek())
                {
                    //去除队列中最大的数
                    maxHeap.Dequeue();
                    maxHeap.Enqueue(arr[i]);
                }

            }

        }
    }

 

 

 

 

 

 

 

 

 

 

  

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/155691.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2022年7月3日 下午1:36
下一篇 2022年7月3日 下午1:46


相关推荐

  • DB9 公头母头引脚定义及连接

    DB9 公头母头引脚定义及连接

    DB9 公头母头引脚定义及连接

    全栈程序员-站长的头像 全栈程序员-站长
    2021年12月4日
    70
  • 前端面试题 vue_vue面试题必问

    前端面试题 vue_vue面试题必问

    前端面试题 vue_vue面试题必问1.自我介绍2分钟，200-300个字，主旨自己基本情况，工作经历，优点，兴趣爱好，职业规划，邀约2.vue面试题1.v-show和v-if区别的区别：v-show通过cssdisplay控制显示和隐藏，v-if组件真正的渲染和销毁，而不是显示和隐藏，频繁切换状态使用v-show否则v-if2.为何v-for要用key快速查找到节点，减少渲染次数，提升渲染性能3.描述vue组件声明周期mm单组件声明周期图挂载：beforeCreate=>created=

    全栈程序员-站长的头像 全栈程序员-站长
    2025年10月2日
    6
  • c++中delete什么意思_delete和delete()

    c++中delete什么意思_delete和delete()

    c++中delete什么意思_delete和delete()一直对C++中的delete和delete[]的区别不甚了解，今天遇到了，上网查了一下，得出了结论。做个备份，以免丢失。C++告诉我们在回收用new分配的单个对象的内存空间的时候用delet

    全栈程序员-站长的头像 全栈程序员-站长
    2022年8月2日
    8
  • UWB定位技术

    UWB定位技术

    UWB定位技术室内定位 UWB 测距及定位原理我们都知道卫星信号在室内会被严重的影响 从而导致 GPS 或是北斗无法发定位 所以在室内定位主要采用无线通讯 基站定位 惯导定位等多种技术集成形成一套室内位置定位体系 从而实现人员 物体等在室内空间中的位置监控 除通讯网络的蜂窝定位技术外 常见的室内无线定位技术还有 Wi Fi 蓝牙 红外线 超宽带 RFID ZigBee 和超声波 今天我们来谈谈 UWB

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月20日
    2
  • 渗透测试笔记汇总_渗透测试怎么做

    渗透测试笔记汇总_渗透测试怎么做

    渗透测试笔记汇总_渗透测试怎么做【拿shell】1.直接上传aspasajspcerphpaspxhtrcdx格式的木马，不行就利用IIS6.0解析漏洞”:1.asp;1.jpg/1.asp;.jpg/1.asp;jpg/1.asp;.xls2.上传图片木马遇到拦截系统，连图片木马都上传不了，记事本打开图片木马在代码最前面加上gif89a，一般就能逃过拦截系统了。3.上传图片木马把地址复制到数据库…

    全栈程序员-站长的头像 全栈程序员-站长
    2026年2月10日
    11
  • mybatisPlus填坑之逻辑删除

    mybatisPlus填坑之逻辑删除

    mybatisPlus填坑之逻辑删除网上大部分的关于mybatisPlus的逻辑删除的配置介绍都是有问题的，原因可能是官网已经做了更新！！！错误如图：正确的配置是：SpringBoot配置方式： application.yml加入配置(如果你的默认值和mp默认的一样,该配置可无): yml文件（区别是多了一个路径db-config，同学们细看了） mybatis-plus:global-c…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月5日
    169

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号