【JavaScript数据结构系列】04-优先队列PriorityQueue

汇维小哥 發表於 2019-12-29 22:19:00

【JavaScript数据结构系列】04-优先队列PriorityQueue

<h1 id="javascript数据结构系列04-优先队列priorityqueue">【JavaScript数据结构系列】04-优先队列PriorityQueue</h1>
<blockquote>
码路工人 CoderMonkey 
转载请注明作者与出处
</blockquote>
 

## 1. 认识优先级队列
经典的案例场景：
<ul>
<li>登机时经济舱的普通队列与头等舱的优先级队列</li>
<li>股票交易时基于时间和价格的成交规则上，量大优先的优先级队列</li>
</ul>
再用我们打饭的例子： 假定规则：饥饿等级0级最高，需要马上进食 下图同学C优先级高于同学B，插队在同学A后面 <img src="https://cdn.nlark.com/yuque/0/2019/png/561211/1574845941692-5a3c117a-0a06-46c9-8fb7-10054aad8aa0.png#align=left&display=inline&height=460&name=PriorityQueue.png&originHeight=463&originWidth=751&size=21258&status=done&style=none&width=746">

<h2 id="2-代码实现">2. 代码实现</h2>
<blockquote>
注： 
ES6 版的代码实现请查看 npm 包 data-struct-js 代码 
Github/Gitee 上都能找到
<blockquote>
<blockquote>
npm install data-struct-js
</blockquote>
</blockquote>
</blockquote>
 在队列 Queue 的基础上，我们来实现一下优先级队列。
<ul>
<li>优先级队列只在入队操作上与普通队列不同，其它方法相同</li>
<li>参考上一节里的基于栈实现的队列，也稍稍修改下队列实现的代码</li>
</ul>
<blockquote>
入队操作实现分析：
<ul>
<li>在创建元素时，我们需要一个优先级参数/字段（priority）</li>
<li>并对优先级做检查，以及默认值设置</li>
<li>空队列时直接入队</li>
<li>非空时，从队列头部开始比对每一个元素，新元素优先级高时插入</li>
<li>比对到最后一个也没能插入时（新元素优先级最低）添加到队尾</li>
</ul>
</blockquote>
主要是 enqueue 方法和 QueueElement 的封装。
<pre><code class="language-javascript">// 优先队列
function PriorityQueue() {
this.__items = []

/**
*队列元素对象
*优先级默认为最低
*/
function QueueElement(element, priority) {
// check priority
if(typeof(priority) != 'number' || Number.isNaN(priority)) {
 // min-level: Infinity
 priority = Infinity
}
this.__element = element
// max-level: 0
this.__priority = priority

QueueElement.prototype.priority = function() {
 return this.__priority
}

QueueElement.prototype.toString = function() {
 return this.__element.toString.apply(this.__element)
}
}

// 入队方法
PriorityQueue.prototype.enqueue = function(element, priority) {
var queueElement = new QueueElement(element, priority)

// 空队列时直接入队
if(this.__items.length === 0) {
 this.__items.push(queueElement)
}
// 非空队列入队需比较优先级
else {
 var added = false
 for(var i=0;i<this.__items.length;i++) {
 if(queueElement.priority() < this.__items.priority()) {
 this.__items.splice(i, 0, queueElement)
 added = true
 break
 }
 }
 if(!added) {
 this.__items.push(queueElement)
 }
}
}
}
</code></pre>
<blockquote>
自己封装的优先级队列中优先级priority也可以作为复杂对象上的一个属性，无需另传参数
</blockquote>
完整代码（用到的上一节中的 deepCopy 方法也一并贴上吧）
<blockquote>
PriorityQueue.js 
这里为了方便查看代码写全了， 
实际上重复的部分可以继承普通队列
</blockquote>
<pre><code class="language-javascript">// 优先队列
function PriorityQueue() {
this.__items = []

/**
*队列元素对象
*优先级默认为最低
*/
function QueueElement(element, priority) {
// check priority
if(typeof(priority) != 'number' || Number.isNaN(priority)) {
 // min-level: Infinity
 priority = Infinity
}
this.__element = element
// max-level: 0
this.__priority = priority

QueueElement.prototype.priority = function() {
 return this.__priority
}

QueueElement.prototype.toString = function() {
 return this.__element.toString.apply(this.__element)
}
}

// 入队方法
PriorityQueue.prototype.enqueue = function(element, priority) {
var queueElement = new QueueElement(element, priority)

// 空队列时直接入队
if(this.__items.length === 0) {
 this.__items.push(queueElement)
}
// 非空队列入队需比较优先级
else {
 var added = false
 for(var i=0;i<this.__items.length;i++) {
 if(queueElement.priority() < this.__items.priority()) {
 this.__items.splice(i, 0, queueElement)
 added = true
 break
 }
 }
 if(!added) {
 this.__items.push(queueElement)
 }
}
}

PriorityQueue.prototype.dequeue = function() {
return this.getItems().shift()
}

PriorityQueue.prototype.front = function () {
return this.__items.length === 0 ? undefined : this.getItems()
}

PriorityQueue.prototype.getItems = function() {
return deepCopy(this.__items)
}

PriorityQueue.prototype.isEmpty = function () {
return this.__items.length === 0
}

PriorityQueue.prototype.size = function () {
return this.__items.length
}

PriorityQueue.prototype.clear = function () {
this.__items.length = 0
}

PriorityQueue.prototype.toString = function () {
var arrStr = this.__items.map((qe)=>{
 return qe.toString()
})
return arrStr.join('\r\n')
}
}
</code></pre>
<pre><code class="language-javascript">function deepCopy(source) {
var dest
if(Array.isArray(source)) {
dest = []
for (let i = 0; i < source.length; i++) {
 dest =deepCopy(source)
}
}
else if(toString.call(source) === '') {
dest = {}
for(var p in source){
 if(source.hasOwnProperty(p)){
 dest=deepCopy(source)
 }
}
}
else {
dest = source
}
return dest
}
</code></pre>
测试一下
<pre><code class="language-javascript">var pq = new PriorityQueue()

pq.enqueue({name: 'A-First Element | Priority:1', age: 18, toString: function(){return this.name}}, 1)
pq.enqueue({name: 'B-Second Element | Priority:3', age: 18, toString: function(){return this.name}}, 3)
pq.enqueue({name: 'C-Third Element | Priority:2', age: 18, toString: function(){return this.name}}, 2)

console.log(pq.toString())
</code></pre>
以优先级分别为 1 -> 3 -> 2 的顺序添加元素， 输出结果为：
<pre><code>A-First Element | Priority:1
C-Third Element | Priority:2
B-Second Element | Priority:3
</code></pre>
收工。
<hr>
做了一份 npm 工具包 <code>data-struct-js</code> ， 基于 ES6 实现的 JavaScript 数据结构， 虽然这个小轮子很少会被使用， 也许对于初学者学习 JavaScript 会有点帮助。 只要简单 install 一下即可，感兴趣的话还可以去 GitHub / Gitee 看源码。（来 Star 一个吧）
<pre><code class="language-bash">npm install data-struct-js --save-dev
</code></pre>
<blockquote>
https://github.com/CoderMonkie/data-struct-js 
https://gitee.com/coder-monkey/data-struct-js
</blockquote>
最后，感谢您的阅读和支持~
<hr>
<center>-end-</center>

</div>
<div id="MySignature" role="contentinfo">
<style>.signature { background-color: lightskyblue; padding: 10px; display: inline-flex; border: 1px dashed red }
.emphersize { font-weight: bold; color: darkblue }</style>
<div class="signature" style="display: flex">
 <div>
 作者：码路工人
 公众号：码路工人有力量（Code-Power）
 欢迎关注个人微信公众号 Coder-Power
 一起学习提高吧~
 </div>
 <img src="https://gitee.com/Coding-Worker/picture/raw/master/2021-1-5/1609860559027-qrcode_for_gh_e1903e0c25a7_258.jpg">
</div> 
来源：https://www.cnblogs.com/CoderMonkie/p/js-data-struct-priorityqueue.html

頁: [1]

琼殿技术论坛's Archiver

【JavaScript数据结构系列】04-优先队列PriorityQueue