`
风子柒
  • 浏览: 56345 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

要去哪里找 像你这么好 ——从堆到优先队列的实现

阅读更多
     优先队列,顾名思义,就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结合体,不仅可以存储数据,还可以将这些数据按照我们设定的规则进行排序。

     先说说优先队列的实现吧。有一点需要澄清,很多人一直以为Priority Queue就是一个Priority Heap,这种说法当然是片面的。既然优先队列只是存储数据和排序的结合,那么根据我们学过的知识,可以列出以下的实现方法:无序数组、无序链表、有序数组、有序链表以及二叉查找树,当然还有堆。这些方法在实现中当然也有优先级,下表就是一些方法的实现基本操作的时间性能对比:



图1.一些优先队列的实现方案的时间性能对比


     从这张表里我们可以按照时间复杂度这个优先级来进行一次排序,当然,你会选用最后一种二叉查找树作为实现优先队列的方案,但是实际上我们采用的是堆。堆,就是一种二叉树,堆和二叉查找树是类似的,但是也有些许不同:从形状来看,二叉查找树可以有不同的形状,而堆只能是完全二叉树;在时间性能上,二者并无明显的区别。堆也是有序的,我们一般将其分为大顶堆和小顶堆。小顶堆,顾名思义,就是这个堆的子结点的值小于父结点的值;相反的,大顶堆就是堆的子结点的值都大于父结点的值。
     在实现的时候,我们常常使用基于数组的堆,即堆中的元素保存在一个数组中,而这个数组元素的保存也是按照一定规律的:如果父结点的位置为n,那么,其对应的左右子结点的位置分别是2n+1和2n+2。也就是说,我们在视觉上(如果用画图形象化表示堆的话)和本质上将堆打扮成两种东西,这样既便于理解,也利于实现,本质的实现是用数组是因为考虑到数组的一些性能。
     堆有两个很基本的操作:增加、删除。先来说说增加元素,假设有下面这样一个堆:



     这时候,有一个元素1要添加进来,这时候应该怎么办呢?第一步,将元素添加到堆的最后一个位置:



     第二步,将新加入的元素与其父结点的值进行比较,若新结点的值比其父结点的值要小(就像这个例子一样),那么,交换两个结点的值,重复第二步,直到形成一个小顶堆:






     这样,一个新的小顶堆诞生了!
     然后就是从堆中删除一个元素了,假设在这个新的小顶堆中,我们打算删除堆顶元素:
     第一步,将这个1删掉,假设其结点上当前没有值:





     第二步,将最后一个结点的值放在根的位置,然后进行下滤,比较一下两个子结点的值与根节点的值,将堆顶元素与其子结点中较小的交换,然后重复:










     知道了这些基本的原理,对数据量更大的增加和删除也应该是触类旁通了吧。
     有人会质疑堆中除堆顶元素之外的其他元素的顺序问题:



     比如这里为什么4会放在5的右边兄弟结点上,这明显是受了二叉查找树的影响,因为堆对我们来说,一般只有堆顶元素有用,因此只要保证堆顶元素是最小的就行了(对小顶堆)。

     下面,简单介绍一下sun提供的PriorityQueue的一些基本的方法,以此来较为深入地理解优先队列的实现机制:
     1.下面是PriorityQueue的声明的第一句话:



     这句话表明:sun提供的优先队列是基于优先堆实现的;
     2.下面是声明一个Object数组时的注释:



     由此可知,堆中的元素在数组中的保存方案;并且队列中的优先级最小的元素总是保存在queue[0]中,前提是该优先队列不为空。
     下面是往PriorityQueue中上滤的方法:



     这段代码中,k代表当前加入元素的位置,即最后一个位置+1,x表示要添加的元素。首先得到父结点的值,然后将x的值和父结点的值进行比较,如果子结点的值大于父结点值,不作更改,否则交换两者的值。这个方法主要用于添加元素的时候。与之相对应的有一个下滤方法siftDownComparable(),其功能是向下比较,用在删除元素的实现中;
      接下来就讲添加元素的实现:



     这里可以看到用到了siftUp方法,其实,siftUp中分情况调用了 siftUpUsingComparator()、siftUpComparable()。这在刚才已经介绍了上滤的实现了。这里的添加元素就是上滤的过程。
     当然,我们在使用时,一般使用的方法是这三种:add、poll以及peek,add用以添加元素,其内部是用offer方法实现的,peek用来得到堆顶元素,但是不删除,而poll在返回堆顶元素之后,将堆顶元素删除。

     以上只是对优先队列的简要介绍,作为一个应用比较广泛的数据结构,优先队列还有许许多多奇妙的地方,它们都等着你去发现。

  • 大小: 19.3 KB
  • 大小: 5.1 KB
  • 大小: 5.8 KB
  • 大小: 5.4 KB
  • 大小: 5.6 KB
  • 大小: 5.8 KB
  • 大小: 5.7 KB
  • 大小: 5.8 KB
  • 大小: 5.4 KB
  • 大小: 5.4 KB
  • 大小: 9.3 KB
  • 大小: 15.7 KB
  • 大小: 17.4 KB
  • 大小: 16.4 KB
  • 大小: 8.3 KB
  • 大小: 7.3 KB
  • 大小: 7.4 KB
5
1
分享到:
评论

相关推荐

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

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

    lazy_binomial_heap的python实现——lazy 二项堆——优先队列。

    lazy binomial heaps的oython实现,优先队列。采用双向循环链表实现,api:merge,insert,find_min,extractMin,coalesce_step,updateMin。

    手撸一个优先队列(csdn)————程序.pdf

    在Java中,`java.util.PriorityQueue`是内置的优先队列实现,但这里我们将探讨如何手动实现一个简单的优先队列。 首先,我们需要理解优先队列的核心功能。这个手动实现的优先队列将具备以下特性: 1. **泛型支持**...

    《数据结构——C++实现》(第二版)课本源代码

    《数据结构——C++实现》(第二版)是一本经典的计算机科学教材,专注于介绍各种数据结构及其在C++编程语言中的实现。这本书的核心是通过实际的代码示例帮助读者理解和掌握数据结构的基本概念,这对于任何想要深入...

    安卓Android源码——(堆房子).zip

    堆是一种特殊的数据结构,常用于优先队列的实现,比如Java中的`PriorityQueue`。在这个例子中,可能将堆的概念应用到了Android系统的某些功能或服务上,以帮助开发者理解其工作原理。 "堆房子"可能是指通过构建堆...

    面试求职必会算法——树和堆

    堆常用于实现优先队列,其中最高(或最低)优先级的元素总是位于堆顶。堆排序算法就是利用这一特性,通过构建和调整堆来实现排序。此外,堆还广泛应用于动态规划中的记忆化搜索和Top-K问题。 在面试中,你可能会...

    数据结构 堆的实现

    4. 堆排序:堆可以用来实现快速的排序算法——堆排序。首先,将数组转换为最大堆,然后不断将堆顶元素与末尾元素交换,缩小堆的大小,直到整个数组排序完成。 在标准大学课程中,可能会涉及以下内容: - 堆的理论...

    数据结构——栈和队列

    想象一个堆叠的盘子,新放上去的盘子总是在最上面,要取走盘子时,必须先拿掉最上面的那一个。在计算机中,栈常用于表达式求值、函数调用、回溯算法以及许多其他场景。C语言中,可以使用数组或链表来模拟栈的操作,...

    flatqueue一个非常快速和简单的JavaScript优先队列

    本文将详细介绍flatqueue——一个快速且简单的JavaScript优先队列实现。 一、flatqueue简介 flatqueue由开发者mourner创建,其主要目标是提供一个轻量级且高效的优先队列解决方案。与其他优先队列实现相比,...

    图的相关操作如用到优先队列

    在这个主题中,我们将深入探讨图的两种主要遍历算法——深度优先搜索(DFS)和广度优先搜索(BFS),以及如何利用优先队列在这些操作中找到最短路径和关键路径。 首先,深度优先搜索是一种用于遍历或搜索树或图的...

    基本的数据结构知识——队列

    6. **广度优先搜索(BFS)**:在图或树的遍历算法中,队列常用于BFS,从根节点开始,逐层访问所有节点。 ### 四、队列的拓展 1. **循环队列**:解决线性结构队列满时需要扩容的问题,通过数组的循环特性实现队头和...

    数据结构——堆.pdf

    堆在计算机科学中有很多应用,比如优先队列、堆排序算法、事件调度等。优先队列常用于处理具有优先级的任务,如高优先级任务先执行。堆排序则是一种高效的排序算法,能在O(n log n)的时间复杂度内完成排序。在事件...

    数据结构课程设计——压缩软件(Huffman编码实现)

    2. **创建最小堆**:根据频率建立一个优先队列(最小堆),每个元素都是一个带频率的单字符节点。 3. **合并节点**:每次从队列中取出两个频率最小的节点,合并成一个新的内部节点,新节点的频率等于两个子节点的...

    数据结构实验——分类二叉树和堆排序.doc

    最大堆可以方便地找到当前最大元素,常用于实现优先队列。实验要求实现最大堆的初始化(MaxHeapInit)、删除最大元素(MaxHeapDelete)以及输出排序结果(Displayarray)。 最大堆初始化函数`MaxHeapInit`将数组中...

    《Java数据结构和算法》学习笔记(3)——栈和队列

    PriorityQ可能涉及优先队列的实现,包括如何利用Comparator接口或者Comparable接口来设定元素的优先级,以及在实际问题中的应用,比如堆排序等。 总的来说,掌握栈和队列的基本概念、操作和实现方式,对于提升编程...

    哈夫曼实现压缩解压缩——源代码

    然后,通过构建最小堆(优先队列),将两个频率最小的节点合并成一个新的节点,其频率为两个子节点的频率之和。重复此过程直到只剩下一个节点,这个节点就是哈夫曼树的根节点。 2. **生成哈夫曼编码**:从根节点...

    哈夫曼编码——用树结构实现的

    - 创建一个空的优先队列(最小堆)。 - 对于输入的每个字符及其出现频率,创建一个只含有该字符的单节点二叉树,并将其加入优先队列中。 2. **循环步骤:** - 从优先队列中取出权值最小的两个节点(树)。 - ...

    单元路径——算法分析

    算法的关键在于维护一个优先队列(通常使用二叉堆实现),用来存储未访问节点并按距离排序。初始时,只有起点在队列中,其距离为0;其他节点的距离被初始化为无穷大,表示未被访问。 算法步骤如下: 1. 初始化:...

    合工大数据结构实验 队列.zip

    在实际应用中,队列常常与其他数据结构和算法结合,例如优先队列(Priority Queue)结合了堆的特性,用于实现如事件调度、图的最短路径算法等。此外,队列也是许多高级数据结构如广义表、树和图的基础组件。 总的来...

Global site tag (gtag.js) - Google Analytics