在Unity中实现优先队列

这篇具有很好参考价值的文章主要介绍了在Unity中实现优先队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

在.Net 6,7,8 中C#提供了优先队列PriorityQueue<TElement,TPriority> 类,详情参见官方文档PriorityQueue<TElement,TPriority> 类 (System.Collections.Generic) ,在Unity中想直接使用这个类时,发现不支持,没办法只好自己写一个了,这里讲一下我的实现思路和源码:

优先队列是什么?

百度百科定义:

优先队列是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有

  1.  查找
  2. 插入一个新元素
  3. 删除 一般情况下,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素 。对于优先权相同的元素,可按先进先出次序处理或按任意优先权进行。

简单定义:

优先队列是一种特殊的队列,每次出队时移除队中最大(小)元素。

这篇文章的实现思路基于二叉堆来实现,二叉堆在逻辑上是一个完全二叉树结构。在完全二叉树中,除最低层之外,其他层都被节点填满,最低层尽可能从左到右插入节点。

根据节点的值与子节点的值的大小关系,堆又可以分为最大堆和最小堆

  • 最大堆中,每个节点的值总是大于或等于子节点的值,因此最大堆的根节点就是整个堆的最大值。
  • 最小堆中,每个节点的值总是小于或等于子节点的值,因此最小堆的根节点就是整个堆的最小值。

如何实现优先队列?

完全二叉树结构很容易被数组存储和计算。根据完全二叉树的特性,已知完全二叉树上 i 位置上的节点,我们求得以下信息:

父节点位置:(i - 1) / 2

左孩子节点位置:2i + 1

右孩子节点位置:2i + 2

因此代码中,逻辑结构上基于完全二叉树实现,数据存储基于数组实现。

using System;
using System.Collections.Generic;
using UnityEngine;

namespace Algorithm
{
    public class PriorityQueue<T>{
        private int _size;
        public int Size
        {
            get{
                if (_size < 0)  _size = 0;
                return _size;
            }
            set => _size = value;
        }

        private int _capacity;
        public int Capacity { 
            get{
                if (_capacity < 0) _capacity = 0;
                return _capacity;
            }
            set => _capacity = value;
        }
        
        public T[] _elements;
        
        public bool IsEmpty => _size == 0;
        private T Top => _elements[0];
        
        private readonly IComparer<T> _comparator;
        
        public PriorityQueue(IComparer<T> comparator, int capacity = 1) {
            Size = 0;
            Capacity = capacity;
            _elements = new T[capacity];
            _comparator = comparator;
        }

        public void Enqueue(T element)
        {
            if (Size == Capacity) {
                ExpandCapacity();
            }

            _elements[Size] = element;
            HeapInsert(_elements, Size);
            Size++;
        }

        public T Dequeue()
        {
            if (Size == 0) {
                return default(T);
            }
            
            T element = _elements[0];
            //删除堆顶元素,将堆顶元素交换到最后端
            Swap(_elements, 0, Size - 1);
            Size--;
            Heapify(_elements, 0, Size);
            return element;
        }

        public T Peek()
        {
            return Top;
        }
        
        private void HeapInsert(T[] elements, int index)
        {
            //比较当前节点与父节点之间的大小,从插入位置向上处理。
            while (_comparator.Compare(elements[index], elements[(index - 1) / 2]) > 0)
            {
                Swap(elements, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        public void Clear()
        {
            Size = 0;
        }

        private void Heapify(T[] elements, int index, int size)
        {
            int left = index * 2 + 1;
            while (left < size)
            {
                int comparatorNum = left + 1 < size && _comparator.Compare(elements[left + 1], elements[left]) > 0 ? left + 1 : left;
                comparatorNum = _comparator.Compare(elements[comparatorNum], elements[index]) > 0 ? comparatorNum : index;
                if (comparatorNum == index) {
                    break;
                }
                Swap(elements, comparatorNum, index);
                index = comparatorNum;
                left = index * 2 + 1;
            }
        }

        // 这里借鉴CSDN博客:
        // https://blog.csdn.net/Ilovewolves/article/details/119453154
        private void ExpandCapacity() {
            Capacity = Mathf.CeilToInt(Capacity * 1.5f);
            T[] newElements = new T[Capacity];
            for (int i = 0; i < _elements.Length; i++) {
                newElements[i] = _elements[i];
            }
            _elements = newElements;
        }
        
        private void Swap(T[] elements, int i, int j){
            (elements[i], elements[j]) = (elements[j], elements[i]);
        }
    }
}

代码解释:

实现思路:上述代码中最核心的就是 HeapInsert 和 Heapify。

  • HeapInsert :元素入队时,此时是在队尾,为了满足最大(小)堆特性,保证根节点元素始终是最大(小)值,需要找到插入节点父亲节点进行比较,然后跳转到该父节点位置,继续向上比较,直到根节点。
private void HeapInsert(T[] elements, int index){
    //比较当前节点与父节点之间的大小,从插入位置向上处理。
    while (_comparator.Compare(elements[index], elements[(index - 1) / 2]) > 0){
        Swap(elements, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}
  • Heapify:删除元素时,将指定位置元素与队尾元素交换,并将堆空间减1,此时可能并不满足最大(小)堆特性,因此需要从删除位置,向下调整。具体操作是比较交换后的指定位置元素、该位置的左、右孩子值的大(小),选择较大(小)值做交换,然后跳转到交换位置重复上述操作,直到交换位置大于堆空间Size,结束。
private void Heapify(T[] elements, int index, int size){
    int left = index * 2 + 1;
    while (left < size){
    	int comparatorNum = left + 1 < size && _comparator.Compare(elements[left + 1], elements[left]) > 0 ? left + 1 : left;
        comparatorNum = _comparator.Compare(elements[comparatorNum], elements[index]) > 0 ? comparatorNum : index;
        if (comparatorNum == index) {
            break;
        }
        Swap(elements, comparatorNum, index);
        index = comparatorNum;
        left = index * 2 + 1;
    }
}

总结一下

优先队列是一种常见的数据结构,最核心的部分是在插入元素时(HeapInsert)和删除元素时(Heapify)的处理。基于上述核心代码,还可以实现堆排序算法,如下:

public void HeapSort(int[] nums){
	if(nums == null || nums.Length < 2)
        return;

    for (int i = 0; i < nums.Length; i++){ //O(N)
        HeapInsert(nums, i); //O(logN)
    }

    var heapSize = nums.Length;
    Swap(nums, 0, --heapSize);
    while (heapSize > 0){
        Heapify(nums, 0, heapSize);
        Swap(nums, 0, --heapSize);
    }
}

最后,非常感谢您能看到这里,如果该文章对你有所帮助和启发,也欢迎您能点赞支持,如果有任何疑问和优化建议也非常欢迎各位大佬能够在评论区友好交流,一起学习进步。文章来源地址https://www.toymoban.com/news/detail-793357.html

到了这里,关于在Unity中实现优先队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】优先级队列——堆

    🧧🧧🧧🧧🧧个人主页🎈🎈🎈🎈🎈 🧧🧧🧧🧧🧧数据结构专栏🎈🎈🎈🎈🎈 🧧🧧🧧🧧🧧【数据结构】非线性结构——二叉树🎈🎈🎈🎈🎈 前面介绍过队列,队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能

    2024年04月14日
    浏览(59)
  • 数据结构:优先级队列(堆)

    队列是一种先进先出 (FIFO) 的数据结构 ,但有些情况下, 操作的数据可能带有优先级,一般出队 列时,可能需要优先级高的元素先出队列。 在这种情况下, 数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象 。这种数据结构就是 优先级

    2024年02月08日
    浏览(41)
  • 数据结构与算法-优先级队列

    Gitee上开源的数据结构与算法代码库:数据结构与算法Gitee代码库 优先级队列,按照优先级别依次输出 计算机科学中,堆是一种基于树的数据结构,通常用 完全二叉树 实现。堆的特性如下 在大顶堆中,任意节点 C 与它的父节点 P 符合 P . v a l u e ≥ C . v a l u e P.value geq C.val

    2024年02月13日
    浏览(43)
  • 【数据结构与算法】03 队列(顺序队列--循环队列--优先级队列--链队列)

    队列( queue )是一种常见的数据结构,它遵循先进先出(FIFO)的原则。队列可以理解为一个具有两个端点的线性数据结构,其中一个端点称为\\\"队尾\\\"(rear),用于插入新元素,另一个端点称为\\\"队首\\\"(front),用于移除元素。新元素被插入到队尾,而最早插入的元素总是在队

    2024年02月08日
    浏览(52)
  • python数据结构中实现队列的几种方法

    运行结果: 首尾指针实现 链队 首尾指针实现链队 尾插有头结点实现链队 链队 尾插法 有头结点实现链队 两个栈实现一个队列 list栈

    2024年01月18日
    浏览(41)
  • 数据结构之优先级队列【堆】(Heap)

    目录 1. 优先级队列(Priority Queue) 2.堆的概念 3.堆的存储方式 4.堆的创建 5.用堆模拟实现优先级队列  6.PriorityQueue常用接口介绍 6.1 PriorityQueue的特点 6.2 PriorityQueue几种常见的构造方式 7.top-k问题 8.堆排序 本篇主要内容总结 (1)优先级队列底层是堆来实现的 (2)堆的本质是

    2024年02月01日
    浏览(53)
  • 数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习

    1、本文章适合新学和复习用,都是用c语言实现的,包含了堆的讲解、堆的应用、堆的练习。 2、有图解和代码都注释,放心食用哦 那么开始: 一、什么是堆 堆(Heap)是计算机科学中一类特殊的数据结构,是最高效的优先级队列。堆通常是一个可以被看作一棵完全二叉树的数组

    2024年03月11日
    浏览(41)
  • 数据结构 之 优先级队列(堆) (PriorityQueue)

    🎉欢迎大家观看AUGENSTERN_dc的文章(o゜▽゜)o☆✨✨ 🎉感谢各位读者在百忙之中抽出时间来垂阅我的文章,我会尽我所能向的大家分享我的知识和经验📖 🎉希望我们在一篇篇的文章中能够共同进步!!! 🌈个人主页:AUGENSTERN_dc 🔥个人专栏:C语言 | Java | 数据结构 ⭐个人

    2024年03月20日
    浏览(48)
  • 【一起学习数据结构与算法】优先级队列(堆)

    如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样,我们就引入了 优先级队列 这种数据结构。 优先级队列(priority queue) 是0个或多个元素的集

    2024年01月19日
    浏览(41)
  • 【数据结构】 优先级队列(堆)与堆的建立

    前面介绍过队列, 队列是一种先进先出(FIFO)的数据结构 ,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列,该中场景下,使用队列显然不合适。 比如:在手机上玩游戏的时候,如果有来电,那么系统应该优先处理打进来的电话

    2024年02月10日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包