JS数据结构&算法学习——优先队列

简介: 我们在了解过队列之后,有没有考虑过优先级队列的事情呢?

优先级队列

我们在了解过队列之后,有没有考虑过优先级队列的事情呢?

概念

我们知道普通的队列想要添加元素,元素会被在队尾入队,但是优先级队列它在考虑添加一个元素的时候会考虑添加数据的优先级,即将我们即将插入数据的优先级与其他数据的优先级一一进行比较,在之后我们就可以得到将要添加的元素在队列中正确的位置。

生活中的应用

  1. VIP优先:我们生活中最能体现优先级队列的就是在排队过程中的VIP通道了,当我们在按照队列进行排队的时候,下一个进入的人是VIP,按理说他是应该在队尾添加,但是由于优先级的原因,高于我们这些普通顾客,他就会通过VIP通道被添加到正确的位置
  2. 道德优先:在我们正常排队去挂号的时候,是按照队列来进行排队的,但是会有需要紧急救治的病人,这个时候就体现了优先级的特点,医生会优先救治那些需要紧急救治的病人。

程序应用

在之前的队列中有提到过,线程队列是按照线程次序来执行的,这个时候如果按照线程的优先级大小来排列,就是通过优先级队列来执行

封装

在封装优先级队列之前,我们需要考虑的是我们如何进行优先级比较以及比较规则

当我们的普通的队列拿来看的话,我们是无法对其元素进行比较的,所以我们需要每个元素需要额外的一个能表达该元素优先级的值来体现该元素的优先级,这样我们才能对其优先级进行比较并形成优先级队列,封装如下

function priorityQueue() {
    //队列的属性
    function QueueElement(element, priority) {
      this.element = element
      this.priority = priority
    }
    this.items = []
    //队列的相关操作
    priorityQueue.prototype.enqueue = function (element, priority) {
      //1.创建对象
      var QueueElement = new QueueElement(element, priority)
      this.items.push(element)
    }
}
复制代码

大家可以明显的注意到,我们在优先级队列这个类中又声明了一个类,由于元素具有原本的值与优先级两个数据,所以我们需要在类中再声明一个类,之后的操作封装也是在函数中创建新类,其中element为数据,priority为优先级

那么我们现在开始考虑我们如何得去比较并按优先级排序

  1. 当队列没有元素,只需要添加元素,无序比较
  2. 当队列中有元素,我们需要将添加的元素与前一个数据比较,若小则再比较,直到遇到优先级大的并插入到后面
priorityQueue.prototype.enqueue = function (element, priority) {
      var QueueElement = new QueueElement(element, priority)
      if (this.items.length == 0) {
          this.items.push(QueueElement)
      } else {
          var add = false
          for (let i = 0; i < this.items.length; i++){
              if (QueueElement.priority < this.items[i]){
                  this.items.splice(i,0,QueueElement)
                  add = true
                  break
              }
          }
          if(!add) {
              this.items.push(QueueElement)
          }
      }
}
复制代码

在这里我们首先会进行对队列是否为空判断,可以用自己封装的isEmpty也可以使用length直接进行判断,如果为空则直接插入,接下里如果队列不为空,则声明一个变量表达状态,如果与前面的元素进行比较,优先级都比被添加元素大的话add为false,则执行下面的部分,直接添加到队尾,如果找到了优先级小的元素,则使用splice的方法来进行插入


相关文章
|
2月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
157 4
|
3天前
|
负载均衡 算法
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
51 11
架构学习:7种负载均衡算法策略
|
9天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
31 2
|
25天前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
56 20
|
2月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
2月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
130 23
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
79 1
|
2月前
|
JavaScript 前端开发 索引
JavaScript学习第二章--字符串
本文介绍了JavaScript中的字符串处理,包括普通字符串和模板字符串的使用方法及常见字符串操作方法如`charAt`、`concat`、`endsWith`等,适合前端学习者参考。作者是一位热爱前端技术的大一学生,专注于分享实用的编程技巧。
38 2
|
2月前
|
存储 JavaScript 前端开发
JavaScript学习第一章
本文档介绍了JavaScript的基础知识,包括其在网页中的作用、如何通过JavaScript动态设置HTML元素的CSS属性,以及JavaScript中的变量类型(`var`、`let`、`const`)和数据类型(基本数据类型与引用数据类型)。通过实例代码详细解释了JavaScript的核心概念,适合初学者入门学习。
61 1
|
2月前
|
算法 vr&ar 计算机视觉
数据结构之洪水填充算法(DFS)
洪水填充算法是一种基于深度优先搜索(DFS)的图像处理技术,主要用于区域填充和图像分割。通过递归或栈的方式探索图像中的连通区域并进行颜色替换。本文介绍了算法的基本原理、数据结构设计(如链表和栈)、核心代码实现及应用实例,展示了算法在图像编辑等领域的高效性和灵活性。同时,文中也讨论了算法的优缺点,如实现简单但可能存在堆栈溢出的风险等。
77 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等