功能：每次插入和弹出都能保证头部元素是集合中的最小值。
示例1：排序，时间复再度O(logN)。（堆排序）
//需要排序的原始集合
private List<int> list = new List<int>(){ 1, 12, 34, 234, 1, 90,-25,24,-54555, 5,-56, 12, 5,6, 151, 2, -55, 0, -125, -5, -21341, 123, -2, -12313, 123, 352 };
void Start()
{
StringBuilder sb = new StringBuilder("原始集合:");
foreach (int item in list)
sb.AppendFormat("{0},",item.ToString());
sb.Remove(sb.Length - 1, 1);
Ib_Log.Info(sb.ToString());
sb.Clear();
sb.Append("升序排序:");
PriorityQueue<int,int> priorityQueue = new PriorityQueue<int,int>();
//将所有元素插入优先队列。
foreach(var item in list) priorityQueue.Push(item,item);
int cnt = priorityQueue.Count;
for (int i = 0; i < cnt; i++)
{
//依次弹出头部元素。每次弹出都会重新维护最小堆，保证头元素是最小值。
sb.Append(priorityQueue.Pop());
sb.Append(",");
}
sb.Remove(sb.Length - 1, 1);
将传入优先队列的Value值*-1后，即可得到降序排列。
//用-item作为值传入。 foreach(var item in list) priorityQueue.Push(item,-item);
示例2：优化A*算法
A*中每次需要选择一个权重最低的点，可以用优先队列进行优化。每次获取权重最小的点，直接排序需要O(N)的时间，通过优先队列弹出只需要O(logN)的时间。
IEnumerator AStar(Vector3Int _initialPos, Vector3Int _endPos)
{
tMap.ClearAllTiles(); //清空演示的网格 与算法无关
float D = 0.95f; //g代价的系数，系数<1，越小越趋近终点，>1趋近起点
var openList = new PriorityQueue<AStarGrid, float>();
var closeList = new HashSet<Vector3Int>();
var map = new Dictionary<Vector3Int, AStarGrid>();
AStarGrid initialGrid = new() //起始点
{
aPos = _initialPos,
parent = null
};
openList.Push(initialGrid, 0); //起始点加入openlist
var cGrid = openList.Top();
while (openList.Count > 0 && cGrid.aPos != _endPos)
{
cGrid = openList.Pop(); //从openlist中取出f最小的AStarGrid
map.Remove(cGrid.aPos);
if (JPS_ShowSlow) //演示，与算法无关
{
yield return new WaitForFixedUpdate();
tMap.SetTile(cGrid.aPos, tTb);
}
if (cGrid.aPos == _endPos) //找到终点
{
Debug.Log("A*Found" + closeList.Count);
CalFollowTimeCost_Follow();
DrawLineByAStarGrid(cGrid); //画路径
yield break;
}
closeList.Add(cGrid.aPos); //加入closeList
for (int i = 0; i < dir8.Length - (fourDir ? 4 : 0); i++) //fourDir = true 则判断四个方向
{
int x = cGrid.aPos.x + dir8[i].x;
int y = cGrid.aPos.y + dir8[i].y;
var nPos = new Vector3Int(x, y);
var nGrid = new AStarGrid { aPos = nPos };
//判断该点是否合法，未越界，不是障碍物，不在closeList中
if (nPos.x <= 0 || nPos.x >= 2 * currentX || nPos.y <= 0 || nPos.y >= 2 * currentY ||
wall.GetTile(nPos) != null || closeList.Contains(nPos))
continue;
nGrid.g = D * (fourDir ? 1 : Mathf.Sqrt(dir8[i].x * dir8[i].x + dir8[i].y * dir8[i].y)) + cGrid.g; //计算g
nGrid.h = fourDir ? H_Manhattan(nGrid.aPos, _endPos) : H(nGrid.aPos, _endPos); //计算h
//查找openlist中是否有该点
if (!map.ContainsKey(nGrid.aPos)) //若没有有该点，则加入openlist
{
nGrid.parent = cGrid;
FollowCost++; //与算法无关
openList.Push(nGrid, nGrid.F);
map.Add(nGrid.aPos, nGrid);
if (JPS_ShowSlow)
{
tMap.SetTile(nPos, jTb);
}
if (ShowF) CreateText(nGrid.aPos, nGrid.F.ToString("#0.0"), Color.blue);
}
else //若有，且当前点的g小于原来点g，则重新计算g+h（当前点覆盖原来点）
{
if (nGrid.g < map[nGrid.aPos].g)
{
nGrid = cGrid;
}
if (ShowF) CreateText(nGrid.aPos, nGrid.F.ToString("#0.0"), Color.red);
}
}
}
yield break;
}
源码：
namespace Ib_Core
{
using System.Collections.Generic;
using System;
namespace Ib_Collections
{
/// <summary>
/// 按Value升序排序的优先队列。Value需要继承IComparable接口
/// </summary>
/// <typeparam name="TKey">键</typeparam>
/// <typeparam name="TValue">值</typeparam>
public class PriorityQueue<TKey, TValue> where TValue : IComparable<TValue>
{
private List<(TKey, TValue)> list;
private int cnt;
public int Count => cnt;
public PriorityQueue(int capacity = 4)
{
list = new List<(TKey, TValue)>(capacity);
cnt = 0;
}
public TKey Top() => Count > 0 ? list[0].Item1 : default;
/// <summary>
/// 通过元组插入元素
/// </summary>
/// <param name="pair"></param>
public void Push((TKey, TValue) pair)
{
if (cnt < 0) cnt = 0;
cnt++;
if (cnt <= list.Count)
{
list[cnt - 1] = pair;
}
else list.Add(pair);
SwapUp(Count - 1);
}
/// <summary>
/// 通过键值对插入元素
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
public void Push(TKey a, TValue b)
{
var pair = (a, b);
Push(pair);
}
/// <summary>
/// 弹出顶部元素。并重新维护最小堆
/// </summary>
/// <returns></returns>
public TKey Pop()
{
var re = list[0].Item1;
list[0] = list[Count - 1];
cnt--;
SwapDown(0);
return re;
}
/// <summary>
/// 清除元素内容
/// </summary>
public void Clear()
{
list.Clear();
cnt = 0;
}
#region 构造堆
/// <summary>
/// 向上建堆
/// </summary>
/// <param name="index"></param>
private void SwapUp(int index)
{
if (index <= 0) return;
int top;
if (index % 2 == 0) top = (index - 2) / 2;
else top = (index - 1) / 2;
if (list[top].Item2.CompareTo(list[index].Item2) > 0)
{
(list[top], list[index]) = (list[index], list[top]);
SwapUp(top);
}
}
/// <summary>
/// 向下建堆
/// </summary>
/// <param name="index"></param>
private void SwapDown(int index)
{
int l = (index * 2) + 1;
int r = (index * 2) + 2;
if (l >= Count) return;
int nextIndex = -1;
if (list[index].Item2.CompareTo(list[l].Item2) > 0)
{
nextIndex = l;
}
if (r < Count && list[index].Item2.CompareTo(list[r].Item2) > 0)
{
if (nextIndex == -1 || list[l].Item2.CompareTo(list[r].Item2) > 0)
{
nextIndex = r;
}
}
if (nextIndex == -1) return;
(list[nextIndex], list[index]) = (list[index], list[nextIndex]);
SwapDown(nextIndex);
}
#endregion
}
}
}
评论（0）
暂无评论