优先队列(堆)
1.优先队列模型:
优先队列是允许下列两种操作的数据结构:insert(插入)以及deleteMin(删除最小者)。insert操作等价于入队,而deleteMin操作则等价于出队,它的工作是找到,返回并删除优先队列中的最小元素。
2.二叉堆:
结构性质:
堆是一棵完全二叉树---深度为h的二叉树,其他各层的节点数都达到了最大,h层的节点也是从左向右填入的。由于完全二叉树很有规律,所以可以用数组来存储完全二叉树中的节点。该数组0位置空出,从下表为1的位置开始填充。以广度遍历存储。
堆序性质:
父母节点的关键字不大于孩子节点的关键字(除根节点,因为根节点没有父母节点)。这样我们就能很快的找到优先队列中的最小元素。
基本的堆操作:
insert(插入):
首先我们在堆中下一个位置创建一个空穴。如果待插入元素X放在空穴中不违反堆序性质,那插入完成。否则,我们把空穴的父节点移到空穴中,这样空穴就朝着根的方向上冒一步。继续该过程直到X能被放到空穴中为止。这种策略叫做“上滤”。
deleteMin(删除最小元):
我们直到堆中最小元为根节点所代表的元素,那么删除最小元就是将根节点删除,然后再根节点处建立一个空穴。由于堆中少了一个元素,因此,堆中最后一个元素X必须移到某个位置。然后我们将空穴的两个儿子中较小的一个放在根节点处,这样就把空穴向下推了一层。重复该步骤直到X可以被放入空穴中。这种策略叫做“下滤”。
其他堆操作:
1.decreaseKey(降低关键字的值):decreaseKey(p,x)操作降低在位置p处的值,降低幅度为正的量x。由于可能破坏堆序性质,因此必须通过上滤进行调整。该操作可以使程序优先执行。
2.increaseKey(增加关键字的值):increaseKey(p,x)操作增加在位置p处的值,增加幅度为正的量x。可以用下滤来完成。许多调度程序自动的降低正在过多消耗CPU时间的进程的优先级。
3.delete(删除):delete(p)操作删除堆中位置p上的节点。该操作优先通过decreaseKey(p,∞)然后在进行deleteMin操作,当一个进程被用户终止时,必须从优先队列中除去。
4.buildHeap(构建堆):二叉堆是由一些项的初始结合构造而得。可以使用N个相继的insert操作来完成。注意,这个算法中每个insert将花费O(1)平均时间以及O(NlogN)的最坏时间,所以该算法的总运行时间是O(N)而不是O(NlogN)的最坏时间。
3.d-堆
d-堆是二叉堆的推广,它就像二叉堆,只不过所有的节点都有d个儿子(因此二叉堆也可叫做2-堆)。
分享到:
相关推荐
用c++的STL实现大根堆和小根堆,实现相当方便简单,优先队列效率好
用C语言实现一个优先队列;压缩文件中包括三个文件:1.HeapQueue.h优先队列源代码,2.main.cpp测试主函数;3.HeapQueue.h使用说明
本程序主要由堆来实现优先队列的数据结构,主要有优先队列的删除,插入。算法复杂度为logn
大根堆,小根堆,优先队列,堆排序,模版。
利用堆实现的优先队列实质是一棵顺序存储的二叉树!所以具有很好的时间"空间性能!比传统的优先队列具有更广泛的应用前景!可在计算机的各种排队算法中推广应用
堆排序实现优先队列,利用优先队列做了一个小程序,有兴趣看看
构建最大堆,维护最大堆,堆排序,以及对在优先队列中的应用。对最大优先队列执行以下操作:向队列中插入新元素,增加某个元素的值,去掉并返回队列中的最大值并保证最大队的性质
C语言 堆 优先队列
数据结构,课程设计优先队列实验报告 用最大堆实现的优先队列
查询最大优先队列的元素,和最小优先队列的元素,时间复杂度为o(1) 因为数组的第一个元素便是我们所需要得要的元素。 而插入操作,只要判断应该插入那棵树,也将是O(1),然而之后需要调整,此时的时间...
优先队列的数据结构是由大顶堆来实现的,每次优先输出最大优先权值。 有搜索优先权最大的值、插入元素值、删除最大优先权值三个主要操作。
本文提出一种基于K 叉树的优先队列的算法, 通过建立K 叉树堆的数据结构, 从n 个元素中 得到m 个元素的优先队列, 其算法的最坏时间复杂度为O (2m log2n + 2n ). 本算法是基于二叉树堆 的优先队列算法的推广, 并具有较...
一. 优先队列的定义 优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除。 本程序的实现 二. 实现本优先队列的初始化,查找,插入,删除操作,...
用c写的优先队列算法,本人觉得这个还是很好用的,方便,强力推荐
优先队列的基本结构:二叉堆、d堆、左式堆、斜堆
优先队列PriorityQueue,_堆Heap【数据结构和算法入门8】
优先队列通常使用二叉堆(包括最大堆和最小堆)来实现,因为堆的性质使得插入和删除最大(或最小)元素的操作可以在对数时间内完成。这使得优先队列在处理大量数据时具有高效的性能。 总的来说,优先队列是一种非常...
两部分代码:静态空间与动态空间实现堆的各种操作,以及利用这些操作实现最大优先队列的vc源码。其中算法思想主要是依据《算法导论》堆的介绍,以及表的扩张与收缩章节内容(动态部分)
利用优先队列(大顶堆)解决轮廓线问题,广东工业大学教程,还不错的