A star前置算法优先队列

A* 寻路算法 其中最重要的就是如何确保我们每次走的都是权值最小的路径这样就可以保证我们寻找的路径是最优的。

优先队列

优先队列是实现A*寻路算法的时候根据权重找出对应的结点很好的方法。

什么是优先队列

优先队列是0个元素和多个元素的集合，每一个元素都有一个优先权限，我们可以对这个队列进行的操作有 插入，删除，当我们
首先优先队列 一般是由满二叉堆来实现的 而二叉堆逻辑上是一个满二叉树。

什么是满二叉树

假设一个二叉树由k层 ，在k-1层之前 每一层的结点的都是2^(k-1-1) 而且第二层的结点都是从最左边网友排列的
根据子节点和父节点的关系 又可以分为最大堆，最小堆
最大堆：每一个结点的值总是大于或者等于子节点的值，因此最大堆的跟节点就是堆的最大值
最小堆：每一个结点的值总是小于或者等于子节点的值，因此最小堆的跟节点就是堆的最小值

假节点为i
父节点 （i-1）/ 2
左子结点 2i+1
右子结点 2i+2

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

namespace UIRANK;
class Program
{
    static void Main(string[] args)
    {
        PriorityQueue<int> priorityQueue = new PriorityQueue<int>();

        
        priorityQueue.EnQuene(1);
        priorityQueue.EnQuene(2);
        priorityQueue.EnQuene(3);
        priorityQueue.EnQuene(4);
        priorityQueue.EnQuene(5);
        priorityQueue.EnQuene(6);
        priorityQueue.EnQuene(5);
        priorityQueue.EnQuene(5);
        priorityQueue.EnQuene(5);
        priorityQueue.EnQuene(5);
        priorityQueue.EnQuene(9);
        Console.WriteLine(priorityQueue.Size);
        Console.WriteLine(priorityQueue.Capacity);
        Console.WriteLine(priorityQueue.Peek());
        Console.WriteLine(priorityQueue.DeQuene());
        Console.WriteLine(priorityQueue.Size);
        Console.WriteLine(priorityQueue.Peek());

        Console.ReadKey();
    }



}
/// 使用的是范型类，并且规定了T只能是可以比较的类型
class PriorityQueue<T> where T : IComparable<T> {
    // 数组的范围
    private int _capacity;
    public int Capacity {

        get {
            if (_capacity < 0) {
                _capacity = 0;

            }
            return _capacity;
        }

        set {
            _capacity = value;
        }
    }
	// 当前数组内存了多少个元素
    private int _size;

    public int Size {
        get {
            if (_size < 0) {
                _size = 0;
            }
            return _size;
        }

        set => _size = value;
    }


    private T[] elements;
    IComparer<T> _comparer;
	// 介绍一下这个构造函数，首先是已经给参数一个默认为10的范围，因为这里要使用到比较函数可能有的时候需要我们根据需求自定义比较所以就用到IComparer这个接口用来让我们使用自定义的比较函数
	// 这个this 表示的调用了第二个构造函数 ，只是传了一个默认的比较器（不想自定义的时候使用）
    public PriorityQueue(int capacity = 10) : this(Comparer<T>.Default, capacity) { }

    public PriorityQueue(IComparer<T> comparer, int capacity = 10) {
        _comparer = comparer ?? Comparer<T>.Default;
        Size = 0;
        Capacity = capacity;
        elements = new T[capacity];
    }

	// 是否为空
    public bool isEmpty => Size == 0;

    private T Top => elements[0];
	// 获得队列最前面的元素（最大值）
    public T Peek() {
        if (isEmpty) {
            throw new Exception("当前队列中没有元素");
        }
        return Top;
    }
    /// 添加元素
    public void EnQuene(T data) {
        if (Size == Capacity) {
            ExtendCapacity();
        }
        elements[Size] = data;
        HeapInsert(Size);
        Size++;
    }
    /// 删除队列最前面的元素 
    public T? DeQuene() {
        if (Size == 0) {
            return default(T);
        }

        T element = elements[0];
        // 删除栈顶的元素然后交换到栈尾
        Swap(elements,0,Size-1);
        Size--;
        //将剩下的元素继续保持原来的优先队列 
        Heapify(0,Size);
        return element;
    }

    /// <summary>
    /// 删除掉队列最上面的值之后需要重新找到最大的值补上并且保证我们的数据结构还是优先队列。
    /// </summary>
    /// <param name="index"></param>
    /// <param name="size"></param>
    private void Heapify(int index,int size) {
        int left = index * 2 + 1;
        while (left < size) {
            int Customsize = left + 1 < size && _comparer.Compare(elements[left + 1], elements[left]) > 0 ? left + 1 : left;
            if (_comparer.Compare(elements[Customsize], elements[index]) ==0) {
                break;
            }
            Swap(elements, Customsize, index);
            index = Customsize;
            left = index * 2 + 1;
        }
    }


    /// <summary>
    /// 当我们 增加元素之后将该元素与父节点对应的元素进行比较如果比父节点对应的元素大 则进行替换
    /// </summary>
    /// <param name="index"></param>
    private void HeapInsert(int index) {
        while (index > 0 && _comparer.Compare(elements[index], elements[(index-1)/2]) > 0) {
            Swap(elements, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

	/// 动态扩容
    private void ExtendCapacity() {
        Capacity = Capacity * 2;
        T[] newElements = new T[Capacity];
        for (int i = 0; i < elements.Length; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }
	/// 转换两个元素的位置
    private void Swap(T[] tempElements ,int i,int j) {
        var temp = tempElements[i];
        tempElements[i] = tempElements[j];
        tempElements[j] = temp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

这里坐一下提醒：这里使用的是 vs2023 使用的是.net7 其中namespace 没有大括号了，并且没有使用using System; 和 using System.Collections.Generic;
其实.net7 已经有内置的优先队列了，但是unity最新版也只支持 c# 9 对应.net 5 而优先队列是从 .net6 开始支持的。大家感兴趣的可以去官网查看具体信息。