【数据结构和算法:简单方法】谈一谈优先队列的实现

22
• 阅读 1403

【系列文章推荐阅读】

首先回忆一下队列(详细内容移步至队列详解),只要记住八个字即可:先进先出(FIFO),后进后出(LILO)。

就像去医院门诊看病排队时一样:先来的先看,看完先走。

而优先队列的特性正是“优先”二字,“优先”二字意味着打破了“常规”“规则”。

优先队列不再遵守普通队列的先进先出的原则了,如何不遵守呢?

  • 最大优先队列:不管入队顺序如何,谁的值最大谁先出队
  • 最小优先队列:不管入队顺序如何,谁的值最小谁先出队

比如,对于最大优先队列,入队顺序为:14352,出队顺序则为:54321;对于最小优先队列,入队顺序为:14352,出队顺序则为:12345.

举个例子:医院的急诊病例,即便来的晚,也是可以优先看病的,因为生命至上。遇到灾难危险时,群众中会先疏散小孩子。

如果在诸如此类需要讲“优先”的情况下,再去讲什么“先进先出”的排队规则,那就不太好了。

那么该如何实现优先队列呢?

首先,在优先队列中,想要出队元素,肯定要先找到最大值,或者最小值;

其次,优先队列“不讲常规”,所以进队顺序已经不重要了,重要的是找到当前队列中的最大值或最小值。

那么,有没有一个能直接找到最大值或最小值,并不在意其它顺序的方法呢?

有!这个方法就是二叉堆!(详细内容请移步至二叉堆详解

  1. 二叉堆的堆顶是该堆中的最大值或最小值
  2. 插入一个结点,即插入到二叉堆的最末尾,然后会再次调整构成二叉堆
  3. 删除一个结点,即删除堆顶,然后会再次调整构成二叉堆

所以可以借助二叉堆来实现优先队列,最大堆实现最大优先队列,最小堆实现最小优先队列

  1. 出队即把堆顶出队
  2. 入队即向二叉堆中插入一个结点
  3. 出队即删除堆顶

天作之合!完美~

下面是最大优先队列的代码实现。

优先队列的结构体即是二叉堆的结构体:

typedef struct {
    int array[MAXSIZE];
    int length;
} BinaryHeap, PriorityQueue;

入队操作:

/**
 * @description: 最大优先队列入队
 * @param {PriorityQueue} *queue 队列指针
 * @param {int} elem 入队元素
 * @return {*} 无
 */
void en_max_queue(PriorityQueue *queue, int elem)
{
    insert_into_max_heap(queue, elem);
}

出队操作:

/**
 * @description: 最大优先队列出队
 * @param {PriorityQueue} *queue 队列指针
 * @param {int} *elem 保存变量指针
 * @return {*} 无
 */
void de_max_queue(PriorityQueue *queue, int *elem)
{
    delete_from_max_heap(queue, elem);
}

函数 insert_into_max_heapdelete_from_max_heap 的实现在文章【二叉堆的原理及操作】中已经实现了,这里不再赘述。

以上就是优先队列的内容。

完整代码请移步至 GitHub | Gitee 获取。

如有错误,还请指正。

如果觉得写的不错,可以点个赞和关注。后续会有更多数据结构和算法相关文章。

【数据结构和算法:简单方法】谈一谈优先队列的实现

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Wesley13 Wesley13
2年前
Java的编程逻辑
1、run()和start()的区别2、线程的基本属性和方法1.id:一个递增的整数,每创建一个线程就加一2.name3.优先级:从1到10,默认为5,会映射到系统中的优先级。数字越大,要优先级越高4.状态: NEW:还没调用start RUNABLE:正在执行run或者正在等待cup分配
Stella981 Stella981
2年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Easter79 Easter79
2年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
2年前
Java Collection
总结1.优先队列的作用是能保证每次取出的元素都是队列中权值最小的(Java的优先队列每次取最小元素,C的优先队列每次取最大元素)。这里牵涉到了大小关系,元素大小的评判可以通过元素本身的自然顺序(_naturalordering_),也可以通过构造时传入的比较器(_Comparator_,类似于C的仿函数)。2.Java中Prio
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
PriorityBlockingQueue 介绍
PriorityBlockingQueue是一个基于优先级堆的无界的并发安全的优先级队列(FIFO),队列的元素按照其自然顺序进行排序,或者根据构造队列时提供的Comparator进行排序,具体取决于所使用的构造方法。实现原理PriorityBlockingQueue通过使用堆这种数据结构实现将队列中的元素按照某种排序规则进行排序,从而改变先进先
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
4个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这