`
kmplayer
  • 浏览: 508717 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

优先级队列

阅读更多
1,优先级队列是不同于先进先出队列的另一种队列。
最大优先级队列,是这样的一种队列结构,它的内部存放着一系列的元素,每个元素都对应着一个最优级,
最大优先级队列不管各元素的入队顺序,在出队时,总是对应优先级最大的元素出队。

2,优先队列是0个或多个元素的集合,每个元素都有一个优先权或值.
对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.
在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;
在最大优先队列(max priority queue)中,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.

3,。优先级队列一般分最大优先级队列和最小优先级队列
。这两种优先级队列只是为了适应不同场合的需要而进行区分实现,在算法上来讲没有什么本质的不同.

4,最大优先级队列一般用二叉树来实现。因为考虑到,对于最大优先级队列来讲,我们关心的只是最大值,因此,这时的二叉树只需要具备下面这个性质,那么就可以实现了:
性质A:总是让二叉树中的每一个节点的key(也就是优先级)值比该节点的子节点的key值大。
保持性质A就可以在每次出队操作时,直接取根节点得到最大优先级的元素。然后再进行树结构的调整,使得取出根节点之后,二叉树仍然保持性质A。
这样的二叉树可以保证,每个入队和出队的操作都在O(h)的时间内完成(h是树的高度)

5,考虑到这个树要保证的性质只有性质A,那么可以让这棵二叉树总是保持为完全二叉树(且不破坏性质A),这样树高就会是lgn,那么入队和出队操作的时间复杂度就是O(lgn)。这就比较理想了。

6,对于一棵完全二叉树,我们可以用数组(而不是链表)方式来实现。因为对于数组实现的完全二叉树,index为i的节点,它的父节点的index 是i/2,左子节点的index是i*2,右子节点的index是i*2+1。乘2和除2都是可以通过位移来实现的,效率上很好。而且通过保存元素个数,可以O(1)时间只找到处于树的最未的那个元素。用数组来实现还有一个好处,就是不需要在数据结构中再实现对父、子节点的指针存储,这样也省下了不少空间。这些特点都非常适合(也很好地改善了)优先级队列的实现。
分享到:
评论

相关推荐

    队列的应用:优先级队列

    使用顺序存储实现优先级队列,展示优先级队列和普通队列的区别之处。

    一个用堆实现的优先级队列

    优先级队列是一种特殊的数据结构,它按照优先级顺序存储元素,最高优先级的元素总是在队列的前端。在计算机科学中,堆通常被用来实现优先级队列。堆是一种完全二叉树,其中每个父节点的值都大于或等于(最大堆)或...

    优先级队列(堆实现)

    优先级队列是一种特殊的线性数据结构,它在处理元素时遵循特定的优先级规则,通常最高优先级的元素会被最先处理。在Java中,优先级队列是通过`java.util.PriorityQueue`类来实现的,它基于一个二叉堆(Binary Heap)...

    优先级队列cpp文件PriorityQueue.cpp

    优先级队列cpp文件PriorityQueue.cpp

    基于双端堆实现的优先级队列

    dheap(插入元素)、pop_max_dheap(删除最大元素)、pop_min_dheap(删除最小元素),is_dheap(堆验证)五个泛型算法,在此基础上实现了一个能在对数时间内获取最大和最小元素的优先级队列,相当于原stl优先级队列...

    priority queue优先级队列

    算法中优先级队列问题...用堆排序的算法来做的例子

    数据与算法:2基本数据结构7-优先级队列.pdf

    数据结构与算法之优先级队列 优先级队列(Priority Queue)是一种特殊的队列,它不同于一般的先进先出队列,而是每次从队列中取出的是具有最高优先权的元素。优先级队列的实现方式有多种,可以基于有序顺序表、无序...

    第10章-优先级队列2

    优先级队列的设计和实现 在计算机科学中,数据结构是一个非常重要的概念,它直接影响着算法的效率和程序的可读性。其中,优先级队列是一种特殊的数据结构,它支持对数据对象的优先级访问和操作。本章将对优先级队列...

    c语言实现优先级队列

    用c语言实现的,简单易懂,希望对大家有用。

    数据结构课设——小大根交替堆实现的双端优先级队列及应用

    数据结构课设——小大根交替堆实现的双端优先级队列及应用 小大根交替堆是一种特殊的堆结构,它可以同时满足大根堆和小根堆的性质。在本文中,我们将对小大根交替堆实现的双端优先级队列进行详细的分析和设计。 ...

    毕业设计MATLAB_优先级队列.zip

    在毕业设计中,MATLAB 被广泛应用于各种科学计算和数据分析任务,而优先级队列(Priority Queue)是数据结构中的一个重要概念,它在许多算法和应用中扮演着核心角色。优先级队列通常不直接内置在MATLAB中,但可以...

    堆排序、优先级队列(c++模板实现)

    使用c++模板实现的堆排序、优先级队列,在vs2010下编译运行通过。压缩文件里为两个工程文件,如果有vs2010的话解压缩打开sln文件就可以了,没有的话,新建工程将文件复制过去就ok了。如果有问题可以留言。

    PriorityQueue-MEX-Matlab 优先级队列 matlab

    优先级队列是一种特殊的数据结构,它在处理数据时遵循“优先级”原则,即具有较高优先级的元素会先于低优先级的元素被处理。在计算机科学中,优先级队列通常用于调度任务、事件处理和其他需要快速访问最高优先级元素...

    os.rar_优先级 队列

    在"os.rar_优先级 队列"这个主题中,我们将深入探讨操作系统如何利用优先级队列来管理进程,确保高效和公平地执行任务。 首先,进程是操作系统中运行的程序实例。在多任务环境中,操作系统需要决定哪个进程应该获得...

    第10章-优先级队列1

    "优先级队列" 在数据结构中,优先级队列是一种特殊的队列,队列中的每个元素都有一个优先级,队列的出队顺序是按照元素的优先级从高到低的顺序。优先级队列可以用来解决许多实际问题,如任务调度、资源分配等。 本...

Global site tag (gtag.js) - Google Analytics