五、优先队列
访问 www.coding-time.cn 阅读原文动画效果，体验更佳。
在计算机科学中, 优先级队列(priority queue) 是一种抽象数据类型, 它类似于常规的队列或栈, 但每个元素都有与之关联的“优先级”。
在优先队列中, 低优先级的元素之前前面应该是高优先级的元素。 如果两个元素具有相同的优先级, 则根据它们在队列中的顺序是它们的出现顺序即可。
优先队列虽通常用堆来实现,但它在概念上与堆不同。优先队列是一个抽象概念，就像“列表”或“图”这样的抽象概念一样;
正如列表可以用链表或数组实现一样，优先队列可以用堆或各种其他方法实现,例如无序数组。
class PriorityQueue { constructor() { this.queue = []; } // 添加元素到优先队列中 enqueue(element, priority) { const item = { element, priority }; let inserted = false; for (let i = 0; i < this.queue.length; i++) { if (item.priority < this.queue[i].priority) { this.queue.splice(i, 0, item); inserted = true; break; } } if (!inserted) { this.queue.push(item); } } // 从优先队列中移除并返回具有最高优先级的元素 dequeue() { if (this.isEmpty()) { return null; } return this.queue.shift().element; } // 返回具有最高优先级的元素，但不进行移除 front() { if (this.isEmpty()) { return null; } return this.queue[0].element; } // 检查优先队列是否为空 isEmpty() { return this.queue.length === 0; } // 返回优先队列的大小 size() { return this.queue.length; } }const priorityQueue = new PriorityQueue(); priorityQueue.enqueue("apple", 2); priorityQueue.enqueue("banana", 3); priorityQueue.enqueue("orange", 1); console.log(priorityQueue.front()); // 输出: "orange" console.log(priorityQueue.dequeue()); // 输出: "orange" console.log(priorityQueue.size()); // 输出: 2 console.log(priorityQueue.isEmpty()); // 输出: false
3. 参考
∙ YouTube
