在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);
    }
}

最后，非常感谢您能看到这里，如果该文章对你有所帮助和启发，也欢迎您能点赞支持，如果有任何疑问和优化建议也非常欢迎各位大佬能够在评论区友好交流，一起学习进步。