【数据结构与算法】详解什么是优先级队列，并用代码手动实现一个优先级队列

- 日理万妓 2023-03-01 10:08 46阅读 0赞

本系列文章【数据结构与算法】所有完整代码已上传 **github**，想要**完整代码**的小伙伴可以直接去那获取，可以的话欢迎点个**Star**哦~下面放上跳转链接

*  [https://github.com/Lpyexplore/structureAndAlgorithm-JS][https_github.com_Lpyexplore_structureAndAlgorithm-JS]

上一篇文章讲解了队列的相关知识，同时用代码实现了一个队列结构。那么本文将介绍一下另一种特殊的队列结构，叫做 **优先级队列**。

上一篇文章的跳转链接——[【数据结构与算法】详解什么是队列，并用代码手动实现一个队列结构][Link 1]

>  *  公众号：**前端印象**
>  *  不定时有送书活动，记得关注~
>  *  关注后回复对应文字领取：【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

![在这里插入图片描述][20200726083159664.png_x-oss-process_image]

### 数据结构——优先级队列 ###

*  一、什么是优先级队列
 *  二、优先级队列的方法
 *  三、用代码实现优先级队列
 *   *  （1）创建一个构造函数
     *  （2）创建内部构造函数
     *  （3）实现enqueue()方法
     *  （4）实现dequeue()方法
     *  （5）实现front()方法
     *  （6）实现isEmpty()方法
     *  （7）实现size()方法
     *  （8）实现toString()方法
 *  四、优先级队列的补充
 *  五、总结

# 一、什么是优先级队列 #

在了解了什么是**队列**以后，我们再来了解**优先级队列**，顾名思义，优先级队列就是在队列的基础上给每个元素加上了先后顺序，我们仍然拿排队买票的例子来讲解。

普通的排队买票队伍就是一个抽象的队列，如图  
![在这里插入图片描述][2020072322103889.png_x-oss-process_image]  
但是，此时这个买票窗口上贴上了如图上这样几个字  
![在这里插入图片描述][20200723221255807.png_x-oss-process_image]  
此时，某些排队的人就有了比别人优先买到票的权利了。假设 `小人3` 是孕妇，那么她可以排到第一个，比 `小人4` 和 `小人8` 更早的买到票，而 `小人4` 和 `小人8` 都没有特殊身份，但是因为 `小人4` 比 `小人8` 来的早，所以 `小人4` 还是排在 `小人8` 的前面，此时是这样的  
![在这里插入图片描述][20200723221458784.png_x-oss-process_image]  
经过这样一个讲解，相信大家都知道 **优先级队列** 和普通的**队列**的区别了吧。

在向**优先级队列**插入元素时，每个元素有一个自己的号码牌，表示该元素是排在队列的前端还是后端。因此，在优先级队列里，也就没有**先进先出**这样一个结构特点了。

假如现在有这样一个空的优先级队列  
![在这里插入图片描述][20200723222307727.png_x-oss-process_image]  
我们向这个空的优先级队列中插入一个元素 `JavaScript`，并给它一个号码牌 `3`，此时是这样的  
![在这里插入图片描述][202007232225459.png]  
这时我们再向优先级队列中插入一个元素 `python`，也给它一个号码牌 `1`，假设号码牌上的数字越小，在队列中排得越靠前，那么此时是这样的  
![在这里插入图片描述][20200723222735312.png]  
如果再插入一个元素 `Java`，给它一个号码牌 `7`，因为数字 `7` 比 `1` 和 `3` 都小，所以此时的队列是这样的  
![在这里插入图片描述][20200723222825852.png]  
好了，对 **优先级队列** 的讲解就讲到这里，如果还有不明白，欢迎关注文章开头的公众号私聊我或者在本文底下留言评论，我看到会解答。

接下来我们就来讲解一下 **优先级队列** 常用的一些方法吧~

# 二、优先级队列的方法 #

其实优先级队列的方法跟普通队列的方法一模一样，也无非是数据的插入 、删除 、查询等方法，只不过这两者的方法内部实现逻辑有略微的区别，前者比较复杂。

老样子，我们还是先列举一下，优先级队列的方法，如下表

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>含义</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>enqueue()</td> 
   <td>向队列添加元素</td> 
  </tr> 
  <tr> 
   <td>dequeue()</td> 
   <td>删除队列最前端的一个元素，并返回该元素</td> 
  </tr> 
  <tr> 
   <td>front()</td> 
   <td>返回队列前端的元素，但不会移除该元素</td> 
  </tr> 
  <tr> 
   <td>isEmpty()</td> 
   <td>查看队列是否为空</td> 
  </tr> 
  <tr> 
   <td>size()</td> 
   <td>返回队列内元素的个数</td> 
  </tr> 
  <tr> 
   <td>toString()</td> 
   <td>以字符串的形式展示队列内的所有元素</td> 
  </tr> 
 </tbody> 
</table>

# 三、用代码实现优先级队列 #

接下来，我们也还是用JavaScript实现一个基于数组的线性结构的类，因为是基于数组实现的队列，所以我们可以把数组的头部看作是队列的前端，把数组的尾部看作是队列的后端。**这里我们规定数字越小的优先级越大**

## （1）创建一个构造函数 ##

function PriorityQueue() { 
    	//属性
        this.list = []
    }

## （2）创建内部构造函数 ##

这一步还是挺有趣的，我们准备在刚才创建的构造函数的内部再创建一个构造函数，为什么要这么做呢？因为上面讲过，在优先级队列中存储的元素都具有两个值，分别是 `存入的数据` 、`号码牌（优先级）`，所以我们准备创建一个这样的构造函数，来存储这两个值，之后需要插入一个元素时，就可以直接 `new` 一个实例对象出来。

function PriorityQueue() { 
    	//属性
        this.list = []
    	
    	//创建内部构造函数，存储元素的数据和优先级
    	function EachElement(e, num) { 
            this.element = e
            this.priority = num
        }
    }

## （3）实现enqueue()方法 ##

因为优先级队列的方法实现会比普通队列的方法复杂一点，我会讲解一下每个方法的实现思路，方便大家理解。

`enqueue()`方法就是向优先级队列添加一个元素，并自动根据每个元素的优先级插入到合适的位置。

**方法实现思路：**

1.  先创建一个新元素的实例对象，将元素的值和优先级传给该实例对象
2.  先判断队列是否为空。若为空，则直接想队列添加该元素
3.  队列不为空，则从头遍历整个队列，判断我们要添加的元素与队列中的元素哪个优先级更大，然后在合适的位置插入元素
4.  若我们要添加的元素比当前队列中所有元素的优先级都要小，那么直接在队列后端添加该元素

思路讲完了，我们直接来看代码

function PriorityQueue() { 
    	//属性
        this.list = []
    	
    	//创建内部构造函数，存储元素的数据和优先级
    	function EachElement(e, num) { 
            this.element = e
            this.priority = num
        }
    
    	//向队列添加元素
        PriorityQueue.prototype.enqueue = function (e, priority) { 
        	// 1.创建新元素的实例对象
            let element = new EachElement(e, priority)
            
    		// 2.判断队列是否为空
            if(this.list.length === 0) { 
                this.list.push(element)
                return;
            }
            
            // 3.队列不为空，遍历整个队列，比较优先级大小
            for(let i in this.list) { 
                if(element.priority < this.list[i].priority) { 
                    this.list.splice(i, 0, element)
                    return;
                }
            }
            
            // 4.新元素优先级最小，直接添加到队列的后端
            this.list.push(element)
        }
    }

我们来使用一下该方法

let pq = new PriorityQueue()
    
    pq.enqueue('abc', 10)
    pq.enqueue('abb', 1)
    pq.enqueue('cdf', 9)

此时的优先级队列是这样的  
![在这里插入图片描述][20200724083023349.png_x-oss-process_image]  
在上面的基础上，我们再向优先级队列添加一个元素 `eee`，并赋予优先级 `9`，即 `pq.enqueue('eee', 9)`。我们看看此时的优先级是什么样的  
![在这里插入图片描述][20200724085145403.png_x-oss-process_image]  
可以看到，同样的优先级都为9，但我们后添加的元素 `eee` 却排在了先添加的元素 `cdf` 的后面。我们想一下，排队买票，那些有特殊身份的人有权利比我们普通人先买到票，那很正常，但是那些没有特殊身份的普通人都是平等的（优先级相同），那必须得遵守个先来后到了，所以当优先级相同时，先添加的元素永远比后添加的元素靠前。

## （4）实现dequeue()方法 ##

`dequeue()`方法就跟普通队列一样啦，直接删除队列前端的第一个元素即可。

接下来我们来单独实现一下该方法

function PriorityQueue() { 
    	//属性
        this.list = []
    	
    	//创建内部构造函数，存储元素的数据和优先级
    	function EachElement(e, num) { 
            this.element = e
            this.priority = num
        }
    
    	//出列
    	PriorityQueue.prototype.dequeue = function () { 
            return this.list.shift()
        }
    }

我们来使用一下该方法

let pq = new PriorityQueue()
    
    //先添加三个元素
    pq.enqueue('abc', 10)
    pq.enqueue('abb', 1)
    pq.enqueue('cdf', 9)
    
    pq.dequeue()              // 返回值为abb的元素实例对象

此时的优先级队列是这样的  
![在这里插入图片描述][20200724083444620.png_x-oss-process_image]

## （5）实现front()方法 ##

`front()`方法就是获取当前优先级队列前端第一个元素，但不会删除该元素。这个方法也没什么好说的，跟普通队列的方法一样。

接下来我们来单独实现一下该方法

function PriorityQueue() { 
    	//属性
        this.list = []
    	
    	//创建内部构造函数，存储元素的数据和优先级
    	function EachElement(e, num) { 
            this.element = e
            this.priority = num
        }
    
    	//返回优先级队列第一个元素
        PriorityQueue.prototype.front = function () { 
            return this.list[0]
        }
    }

我们来使用一下该方法

let pq = new PriorityQueue()
    
    //先添加三个元素
    pq.enqueue('abc', 10)
    pq.enqueue('abb', 1)
    pq.enqueue('cdf', 9)
    
    pq.front()              // 返回值为abb的元素实例对象

跟`dequeue()`方法有区别，`front()`并没有删除前端的第一个元素，所以此时的优先级队列仍然是这样的  
![在这里插入图片描述][20200724083023349.png_x-oss-process_image]

## （6）实现isEmpty()方法 ##

`isEmpty()`方法是判断优先级队列里是否有元素，即是否为空。实现原理很简单，判断数组长度是否为0就可以了。

接下来我们来单独实现一下该方法

function PriorityQueue() { 
    	//属性
        this.list = []
    	
    	//创建内部构造函数，存储元素的数据和优先级
    	function EachElement(e, num) { 
            this.element = e
            this.priority = num
        }
    
        //判断优先级队列是否为空
        PriorityQueue.prototype.isEmpty = function() { 
            if(this.list.length === 0) { 
                return true
            }
            else { 
                return false
            }
        }
    }

我们来使用一下该方法

let pq = new PriorityQueue()
    
    pq.isEmpty()            //返回 true,因为此时没有添加元素
    
    //先添加三个元素
    pq.enqueue('abc', 10)
    pq.enqueue('abb', 1)
    pq.enqueue('cdf', 9)
    
    pq.isEmpty()            //返回 false,因为此时优先级队列内有三个元素

## （7）实现size()方法 ##

`size()`方法就是判断优先级队列中的元素个数。实现方式也很简单，直接返回数组长度即可。

接下来我们来单独实现一下该方法

function PriorityQueue() { 
    	//属性
        this.list = []
    	
    	//创建内部构造函数，存储元素的数据和优先级
    	function EachElement(e, num) { 
            this.element = e
            this.priority = num
        }
    
        //返回优先级队列的元素个数
        PriorityQueue.prototype.size = function () { 
            return this.list.length
        }
    }

我们来使用一下该方法

let pq= new PriorityQueue()
    
    pq.size()     //返回 0,因为还未向优先级队列添加过元素
    
    //添加三个元素
    pq.enqueue('abc', 10)
    pq.enqueue('abb', 1)
    pq.enqueue('cdf', 9)
    
    pq.size()     //返回 3,因为上面三行代码分别向优先级队列添加了一个元素

## （8）实现toString()方法 ##

`toString()`方法就是将优先级队列内的元素用字符串的方式展示出来（将数组转化成字符串）并返回，与普通队列的 `toString()`方法不同的是，它不仅会将元素的值展示出来，还会展示每个元素的优先级。

接下来我们来单独实现一下该方法

function PriorityQueue() { 
    	//属性
        this.list = []
    	
    	//创建内部构造函数，存储元素的数据和优先级
    	function EachElement(e, num) { 
            this.element = e
            this.priority = num
        }
    
        //返回当前优先级队列
        PriorityQueue.prototype.toString = function () { 
            let string = ''
            for(let i in this.list) { 
                string += `${ this.list[i].element}:${ this.list[i].priority} `
            }
            return string
        }
    }

我们来使用一下该方法

let pq= new PriorityQueue()
    
    pq.enqueue('abc', 10)
    pq.enqueue('abb', 1)
    pq.enqueue('cdf', 9)
    
    pq.toString()     //返回 abb:1 cdf:9 abc:10

# 四、优先级队列的补充 #

本文我们是用数组来实现优先级队列的，但你们有没有发现，当我们每次添加元素时，都需要与优先级队列中的很多元素比较优先级大小，然后再找到一个合适的位置插入元素。因为是以数组形式实现的，所以在该优先级队列里，每一个元素都有自己的下标值，并且我们可以通过下标值直接获取到它。

如下图，现在有一个这样的优先级队列，并且它们的下标值也标在下面  
![在这里插入图片描述][20200725082130864.png_x-oss-process_image]  
然后此时我们准备添加一个值为 `c#`，优先级为 `2` 的元素，那么我们通过遍历队列元素比较优先级发现，应该在下标值为 `1` 的位置插入元素，所以，原本优先级队列中下标值为 `1` 以及之后的所有元素都要向后移动一个位置，即下标值 `+1`，结果如下图  
![在这里插入图片描述][20200725082045492.png_x-oss-process_image]  
因为这个例子中，添加一个元素，要改动 `n-1` 个元素的下标值，可想而知，这是一个非常消耗性能的操作，所以在这里用 **数组** 来实现优先级队列还是有点不合适。

下一篇文章我会开始讲 **链表** ，这种数据结构相对于数组的优势就在于往结构中插入元素性能比较高，不会牵一发而动全身。所以等到之后大家学习了链表，可以回过头来用链表实现一下优先级队列。

# 五、总结 #

优先级队列结构的讲解就到这里了，希望大家对优先级队列有了更深一层的理解。下一篇文章我将讲解一下**链表**。

大家可以关注我，之后我还会一直更新别的数据结构与算法的文章来供大家学习，并且我会把这些文章放到【数据结构与算法】这个专栏里，供大家学习使用。

然后大家可以关注一下我的微信公众号：**前端印象**，等这个专栏的文章完结以后，我会把每种数据结构和算法的笔记放到公众号上，大家可以去那获取。

或者也可以去我的github上获取**完整代码**，欢迎大家点个**Star**

*  [https://github.com/Lpyexplore/structureAndAlgorithm-JS][https_github.com_Lpyexplore_structureAndAlgorithm-JS]

我是Lpyexplore，创作不易，喜欢的加个关注，点个收藏，给个赞~ 带你们在Python爬虫的过程中学习Web前端

[https_github.com_Lpyexplore_structureAndAlgorithm-JS]: https://github.com/Lpyexplore/structureAndAlgorithm-JS
[Link 1]: https://blog.csdn.net/l_ppp/article/details/107491673
[20200726083159664.png_x-oss-process_image]: /images/20230209/f663a5071b0c4a9ab275a503045b7e8c.png
[2020072322103889.png_x-oss-process_image]: /images/20230209/9c04557b43bf4927bd52f19dc41e6ad1.png
[20200723221255807.png_x-oss-process_image]: /images/20230209/6928d35441004c43a17b4b80911f8d86.png
[20200723221458784.png_x-oss-process_image]: /images/20230209/49224ef9d8334c55b248c2e4e84eff47.png
[20200723222307727.png_x-oss-process_image]: /images/20230209/1c3fb4b0dd07475c921544768af3e5ec.png
[202007232225459.png]: /images/20230209/acc65ab5fc2b4450b5de22129439853d.png
[20200723222735312.png]: /images/20230209/d50f600f44244c45ba891b6f1b7d5cce.png
[20200723222825852.png]: /images/20230209/860e338725804a95ae794e27f058a7e9.png
[20200724083023349.png_x-oss-process_image]: /images/20230209/b84e54f499dc489c8041b5be4c0c3ce6.png
[20200724085145403.png_x-oss-process_image]: /images/20230209/4dc9a456ad0749639c3ffc52305c9cbd.png
[20200724083444620.png_x-oss-process_image]: /images/20230209/965405712f4349168c15ec0eb6521dcc.png
[20200725082130864.png_x-oss-process_image]: /images/20230209/230b4a20efa74b8a91639d2b627aef9f.png
[20200725082045492.png_x-oss-process_image]: /images/20230209/1e0784625f9840b9a648c267639edccc.png