在最小生成树Prim算法中,可以利用最小优先级队列来改善时间复杂度,同时在单源最短路径Dijkstra算法中也同样可以利用这种最小优先级队列来改善算法时间复杂度。实现最小优先级队列可以有很多种方式,比如基于二叉最小堆,或者斐波那契堆等。这里是二叉最小堆的C#实现,原理是根据书上的伪代码来的,但有些地方我做了改进,比如书key值改变,原来书上只能变大,这里取掉了这个限制。同时还提供了根据卫星值来选择元素的功能,下面是代码:
/// <summary>
/// 队列元素包装类
/// </summary>
/// <typeparam name="T">实际元素类型</typeparam>
public class QueueElement<T>
{
/// <summary>
/// Key值
/// </summary>
public int KeyValue { get; internal set; }
/// <summary>
/// 实际对象
/// </summary>
public T Element { get; private set; }
public QueueElement(T Item, int KeyVal)
{
KeyValue = KeyVal;
Element = Item;
}
}
/// <summary>
/// 最小优先级队列
/// </summary>
/// <typeparam name="T"></typeparam>
public class MinHeapQueue<T>
{
/// <summary>
/// 队列元素存放,采用List实现.
/// </summary>
private List<QueueElement<T>> _queueValues = new List<QueueElement<T>>();
/// <summary>
/// 队列元素数目
/// </summary>
public int Count
{
get
{
return _queueValues.Count;
}
}
/// <summary>
/// 获取队列Key值最小的元素
/// </summary>
/// <returns></returns>
public T GetMinimum()
{
return _queueValues[0].Element;
}
/// <summary>
/// 从队列中取出Key值最小的元素
/// </summary>
/// <returns></returns>
public T ExtractMin()
{
if (_queueValues.Count <= 0)
{
throw new Exception("队列为空");
}
T theMin = _queueValues[0].Element;
int theTail = Count - 1;
_queueValues[0] = _queueValues[theTail];
_queueValues.RemoveAt(theTail);
MinHeapify(0);
return theMin;
}
/// <summary>
/// 整理堆元素,保持最小堆特性,这个函数跟DownAdjust功能相同
/// </summary>
/// <param name="i"></param>
public void MinHeapify(int i)
{
int HeapSize = Count;
int theL = HeapL(i);
int theR = HeapR(i);
int theLeast = i;
if (theL < HeapSize && _queueValues[theL].KeyValue < _queueValues[theLeast].KeyValue)
{
theLeast = theL;
}
if (theR < HeapSize && _queueValues[theR].KeyValue < _queueValues[theLeast].KeyValue)
{
theLeast = theR;
}
if (theLeast != i)
{
SwapElement(i, theLeast);
MinHeapify(theLeast);
}
}
/// <summary>
/// 改变元素key值
/// </summary>
/// <param name="SelectFunc"></param>
/// <param name="NewKey"></param>
public void ChangeKey(Func<T, bool> SelectFunc, int NewKey)
{
int theIndex = -1;
for (int i = 0; i < Count; i++)
{
if (SelectFunc(_queueValues[i].Element) == true)
{
theIndex = i;
break;
}
}
if (theIndex < 0)
{
return;
}
if (_queueValues[theIndex].KeyValue < NewKey)
{
_queueValues[theIndex].KeyValue = NewKey;
DownAdjust(theIndex);
return;
}
if (_queueValues[theIndex].KeyValue > NewKey)
{
_queueValues[theIndex].KeyValue = NewKey;
UpAdjust(theIndex);
return;
}
}
/// <summary>
/// 沿树根方向整理元素,保持最小堆特性
/// </summary>
/// <param name="i"></param>
private void UpAdjust(int i)
{
int theIndex = i;
int thePIndex = HeapP(theIndex);
while (thePIndex >= 0 && _queueValues[theIndex].KeyValue < _queueValues[thePIndex].KeyValue)
{
SwapElement(thePIndex, theIndex);
theIndex = thePIndex;
thePIndex = HeapP(theIndex);
}
}
/// <summary>
/// 沿树叶方向整理元素,保持最小堆特性
/// </summary>
/// <param name="i"></param>
private void DownAdjust(int i)
{
int HeapSize = Count;
int theL = HeapL(i);
int theR = HeapR(i);
int theLeast = i;
if (theL < HeapSize && _queueValues[theL].KeyValue < _queueValues[theLeast].KeyValue)
{
theLeast = theL;
}
if (theR < HeapSize && _queueValues[theR].KeyValue < _queueValues[theLeast].KeyValue)
{
theLeast = theR;
}
if (theLeast != i)
{
SwapElement(i, theLeast);
DownAdjust(theLeast);
}
}
/// <summary>
/// 改变元素key值
/// </summary>
/// <param name="i"></param>
/// <param name="NewKey"></param>
public void ChangeKey(int i, int NewKey)
{
int theIndex = i;
if (_queueValues[theIndex].KeyValue > NewKey)
{
_queueValues[theIndex].KeyValue = NewKey;
UpAdjust(theIndex);
return;
}
if (_queueValues[theIndex].KeyValue < NewKey)
{
_queueValues[theIndex].KeyValue = NewKey;
DownAdjust(theIndex);
return;
}
}
/// <summary>
/// 删除队列元素
/// </summary>
/// <param name="SelectFunc"></param>
public void HeapDelete(Func<T, bool> SelectFunc)
{
int theIndex = -1;
for (int i = 0; i < Count; i++)
{
if (SelectFunc(_queueValues[i].Element) == true)
{
theIndex = i;
break;
}
}
if (theIndex < 0)
{
return;
}
SwapElement(theIndex, Count - 1);
_queueValues.RemoveAt(Count - 1);
if (theIndex < Count)
{
int theP = HeapP(theIndex);
bool theUp = false;
if (theP >= 0)
{
if (_queueValues[theIndex].KeyValue < _queueValues[theP].KeyValue)
{
UpAdjust(theIndex);
theUp = true;
}
}
if (theUp == false)
{
MinHeapify(theIndex);
}
}
}
/// <summary>
/// 队列元素交换位置
/// </summary>
/// <param name="i"></param>
/// <param name="j"></param>
private void SwapElement(int i, int j)
{
QueueElement<T> theTmp = _queueValues[i];
_queueValues[i] = _queueValues[j];
_queueValues[j] = theTmp;
}
/// <summary>
/// 将元素插入队列
/// </summary>
/// <param name="Element"></param>
/// <param name="Key"></param>
public void HeapInsert(T Element, int Key)
{
_queueValues.Add(new QueueElement<T>(Element, int.MinValue));
ChangeKey(Count - 1, Key);
}
/// <summary>
/// 取节点的左孩子节点
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
private int HeapL(int i)
{
return i * 2 + 1;
}
/// <summary>
/// 取节点的右孩子节点
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
private int HeapR(int i)
{
return i * 2 + 2;
}
/// <summary>
/// 取节点的父节点
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
private int HeapP(int i)
{
return (i + 1) / 2 - 1;
}
}
需要注意的,我前面有篇基于二叉最大堆的优先级队列算法跟这篇很类似,但上篇算法中有小错误,而这篇算法中的优先级队列已通过测试,没问题。大家可对比一下,看错误在哪里。
Ps:既然到首页,还是加点注释.
分享到:
相关推荐
优先队列通常使用二叉堆(包括最大堆和最小堆)来实现,因为堆的性质使得插入和删除最大(或最小)元素的操作可以在对数时间内完成。这使得优先队列在处理大量数据时具有高效的性能。 总的来说,优先队列是一种非常...
leetcode 洗牌 #数据结构与算法(Java描述) Algorithm 算法实例:缓存算法、洗牌算法、雪花算法、...顺式队列、链式队列、优先级队列 顺式栈、链式栈 字符串(模式匹配算法) 二叉搜索树、AVL树、红黑树、字典树 并查集
最低优先级队列 最大优先级队列 堆: 二进制最小堆 二进制最大堆 二项式最小堆 二项式最大堆 斐波那契Min-Heap 斐波那契最大堆 树木: 二进制搜索树 二叉搜索树图 AVL树 AVL树状地图 红黑树 红黑树地图 八叉树 ...
第12章 优先级队列 12.1 定义和应用 12.2 抽象数据类型 12.3 线性表 12.4 堆 12.4.1 定义 12.4.2 大根堆的插入 12.4.3 大根堆的删除 12.4.4 大根堆的初始化 12.4.5 类maxHeap 12.4.6 堆和STL 12.5 左高树 12.5.1 ...
数据结构与算法算法工具箱算法预热贪婪算法分而治之动态编程1 动态编程2 数据结构基本数据结构动态数组和摊销分析优先级队列和不交集哈希表二叉搜索树二叉搜索树2 图上的算法图的分解1 图的分解2 图中的路径1 图2中...
6.5 优先级队列 第7章 快速排序 7.1 快速排序的描述 7.2 快速排序的性能 7.3 快速排序的随机化版本 7.4 快速排序分析 7.4.1 最坏情况分析 7.4.2 期望的运行时间 第8章 线性时间排序 8.1 排序算法...
查找二叉查找树中的最大、最小节点 查找二叉查找树中某个节点的前驱、后继节点 堆 小顶堆 大顶堆 堆排序 优先级队列 利用优先级队列合并 K 个有序数组 求一组动态数据集合的最大 Top K 贪心 最少硬币找零问题 分数...
优先级树和堆……………………… 用数组实现堆……………………… 可并优先队列……………………… 左偏树的定义 …………………… 用左偏树实现可并优先队列 …… 应用 ………………………………… 本章小结 ……...
6.5 优先级队列 第7章 快速排序 7.1 快速排序的描述 7.2 快速排序的性能 7.3 快速排序的随机化版本 7.4 快速排序分析 7.4.1 最坏情况分析 7.4.2 期望的运行时间 第8章 线性时间排序 8.1 排序算法...
优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet 单链表 查找和删除指定链结点 双端链表 链表的效率 抽象数据类型 有序链表 双向链表 迭代器 ...
优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet 单链表 查找和删除指定链结点 双端链表 链表的效率 抽象数据类型 有序链表 双向链表 迭代器 ...
1.堆和栈 (1)数据结构的堆和栈 ...由于堆的这个特性,常用来实现优先队列,堆的存取是随意,这就如同在图书馆的书架上取书,虽然书的摆放是有顺序的,但是想取任意一本时不必像栈一样,先取出前面所有
【数据结构】优先级队列.md 【数据结构】字典树(trie树).md 【数据结构】平衡二叉树(AVL树).md 【数据结构】并查集.md 【数论】快速幂全解(模平方根算法).md 【数论】素数问题.md 2. 刷题 LeetCode&剑指Offer ...
第3篇 基于对象的程序设计 第8章 类和对象 8.1 面向对象程序设计方法概述 8.1.1 什么是面向对象的程序设计 8.1.2 面向对象程序设计的特点 8.1.3 类和对象的作用 8.1.4 面向对象的软件开发 8.2 类的声明和对象的定义...
第3篇 基于对象的程序设计 第8章 类和对象 8.1 面向对象程序设计方法概述 8.1.1 什么是面向对象的程序设计 8.1.2 面向对象程序设计的特点 8.1.3 类和对象的作用 8.1.4 面向对象的软件开发 8.2 类的声明和对象的定义...
要求:输出每个字符出现的次数和编码,其中求最小权值要求用堆实现; 4、营业窗口队列模拟 任务:实现具有n(n=3)个窗口的现实队列模拟,统计每人的等待时间。 要求: 1). 随机产生顾客的到达时间和服务时间存盘。...