摘要:学习优先级队列很重要,因为它被用于许多算法中,例如 Dijkstra 的最短路径算法使用优先级队列。
介绍
先决条件
执行
用例
介绍
优先级队列是一种遵循先进先出原则的数据结构,但它与普通队列有不同的做法。但是它们有什么不同?优先级队列使用优先级意味着任何具有最高优先级的元素都将首先被删除,即使它可能是最后插入的,gif 会很好地解释它。
先决条件
- 如果不遵循链接,请了解 javascript 以及如何在 js 中实现队列
执行
现在是编写代码的时候了,我们已经为优先级队列打下了坚实的基础,现在我们将看到完整的代码,然后将其分解成碎片来理解它。
是时候明白了。
class Elements {
constructor(element, priority) {
this.element = element;
this.priority = priority;
}
}
我们在创建构造函数后创建了一个类并将其命名为元素,但是为什么要这样做,原因很简单,我们创建的类是元素的存储及其优先级,我们会在进行中看到它
class PriorityQueue {
constructor() {
this.collection = [];
}
现在我们正在创建名为 PriorityQueue 的类,我们开始谈论我们在构造函数中创建的内容,并且在构造函数中我们创建了任何名为 collection 的数组,继续前进。
enqueue(element, priority) {
const queue = new Elements(element, priority);
let contain = false;
for (let i = 0; i < this.collection.length; i++) {
if (this.collection[i].priority < queue.priority) {
this.collection.splice(i, 0, queue);
contain = true;
break;
}
}
if (!contain) {
this.collection.push(queue);
}
}
我希望你专心,因为很多事情都是先发生的,我们会把它分解成碎片
enqueue(element, priority) {
const queue = new Elements(element, priority);
let contain = false;
enqueue 方法与普通队列中的方法相同,现在我们所做的是我们初始化了元素类并将其存储在队列变量中,并且包含变量等于 false,我们将了解我们为什么使用它。
for (let i = 0; i < this.collection.length; i++) {
if (this.collection[i].priority < queue.priority) {
this.collection.splice(i, 0, queue);
contain = true;
break;
}
}
我们正在创建一个 for 循环,然后做一件普通的事情,但它是魔法发生的地方,所以你会看到 if 语句在每一口井里检查它,我们正在检查集合优先级是否小于队列变量记住我们创建的那个存储类元素。如果您不了解拼接方法,请查看视频
{% youtube youtube.com/watch?v=t1qDSAUclzI %}
在我们更改了包含并使其成为真的之后,我们打破了循环。
if (!contain) {
this.collection.push(queue);
}
仍然在循环外的方法 enqueue 中,我们检查 contains 是否为真,如果它是我们推入集合。继续。
dequeue() {
return this.collection.shift();
}
peek() {
return this.collection[0];
}
rear() {
return this.collection[this.collection.length - 1];
}
get isEmpty() {
return this.collection.length === 0;
}
get print() {
return console.log(this.collection);
}
我们所做的非常简单,我们将其出列并使用 shift 方法,该方法用于删除数组中的第一个元素。在这个阶段,一切都是简单易懂的。
const pQ = new PriorityQueue();
pQ.enqueue('john', 3);
pQ.enqueue('mike', 1);
pQ.enqueue('log', 2);
pQ.dequeue();
console.log('front of the array', pQ.peek());
console.log('last element', pQ.rear());
pQ.print;
最后,我认为代码中的一切都很简单,很容易理解和消化。如果你做到了这一点,那么你就是下一件大事,只要集中注意力,如果有任何问题我很乐意提供帮助,请保持冷静,但在我们关闭之前,让我们看看终端。
完整代码
class Elements {
constructor(element, priority) {
this.element = element;
this.priority = priority;
}
}
class PriorityQueue {
constructor() {
this.collection = [];
}
enqueue(element, priority) {
const queue = new Elements(element, priority);
let contain = false;
for (let i = 0; i < this.collection.length; i++) {
if (this.collection[i].priority < queue.priority) {
this.collection.splice(i, 0, queue);
contain = true;
break;
}
}
if (!contain) {
this.collection.push(queue);
}
}
dequeue() {
return this.collection.shift();
}
peek() {
return this.collection[0];
}
rear() {
return this.collection[this.collection.length - 1];
}
get isEmpty() {
return this.collection.length === 0;
}
get print() {
return console.log(this.collection);
}
}
const pQ = new PriorityQueue();
pQ.enqueue('john', 3);
pQ.enqueue('mike', 2);
pQ.enqueue('log', 1);
pQ.dequeue();
console.log('front of the array', pQ.peek());
console.log('last element', pQ.rear());
pQ.print;
文章来源:https://pernapps.hashnode.dev/how-to-use-priority-queue-in-javascript