function PriorityQueue() {
this.items = []
// 内部类,用于保存元素和元素的优先级
function QueueElement(ele, priority) {
this.ele = ele
this.priority = priority
}
//优先级队列插入方法
PriorityQueue.prototype.enQueue = (ele, priority) => {
//优先级不为number类型结束本次添加
var type = typeof priority
if (priority % 1 != 0) {
type = 'float'
}
if (typeof (priority) != 'number' || type == 'float') {
// console.error(`Invalid priority data=>'${priority}':${typeof(priority)},need an Integer`)
console.error(`无效的优先级 : ${priority}-->${type},需要传入整型数字`)
return
}
var queueElement = new QueueElement(ele, priority)
//为空则直接插入
if (this.isEmpty()) {
this.items.push(queueElement)
} else {//不为空
var added = false//本次插入标识
for (let a = 0; a < this.items.length; a++) {
//需要插入的元素的优先级小于已存在元素的优先级
if (queueElement.priority < this.items[a].priority) {
//插入
this.items.splice(a, 0, queueElement)
//改变标识符,表示已插入
added = true
//本次循环有插入后终止循环
break
}
}
//循环后未找到已存在元素优先级数字大于插入元素,表示插入元素优先级数字最大,直接在末尾插入
if (!added) {
this.items.push(queueElement)
}
}
}
//移除并返回队列第一个元素
PriorityQueue.prototype.deQueue = () => {
return this.items.shift()
}
//返回队列中第一个元素,不做任何修改
PriorityQueue.prototype.front = () => {
return this.items[0]
}
//返回队列最后一个元素,不做任何修改
PriorityQueue.prototype.end = () => {
return this.items[this.items.length - 1]
}
//队列是否为空
PriorityQueue.prototype.isEmpty = () => {
return this.items.length == 0
}
// 队列包含的元素个数
PriorityQueue.prototype.size = () => {
return this.items.length
}
// toString
PriorityQueue.prototype.toString = () => {
var resultStr = ''
for (var a = 0; a < this.items.length; a++) {
resultStr += this.items[a].ele + '--' + this.items[a].priority + ' , '
}
return resultStr
}
}
var pq = new PriorityQueue()
pq.enQueue('a', '10')
pq.enQueue('b', 5)
pq.enQueue('c', true)
pq.enQueue('d', 2.2)
pq.enQueue('e', 2)
console.log(pq);
console.log(pq.toString());
res:
无效的优先级 : 10-->string,需要传入整型数字
无效的优先级 : true-->boolean,需要传入整型数字
无效的优先级 : 2.2-->float,需要传入整型数字
PriorityQueue {
items: [
QueueElement { ele: 'e', priority: 2 },
QueueElement { ele: 'b', priority: 5 }
]
}
e--2 , b--5 ,
JS数据结构与算法之优先级队列(基于数组)
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...