JavaScript 中的优先队列

2025 年 2 月 16 日 | 阅读 6 分钟

引言

在软件工程和编程改进领域，数据结构在高效地组织和管理数据方面起着至关重要的作用。在这些结构中，优先级队列因其根据优先级级别处理元素的 क्षमता 而脱颖而出。在 JavaScript 中，一种灵活且广泛使用的编程语言，优先级队列为开发人员提供了管理各种应用程序中数据的基本工具。让我们深入探讨 JavaScript 中优先级队列的概念，并探讨如何实现和使用它们。

理解优先队列

优先级队列是一种动态数据结构，其中每个元素都被分配一个优先级。优先级较高的元素先于优先级较低的元素得到服务。与普通队列（其中先添加的元素先被删除（先进先出 (FIFO)））不同，优先级队列根据元素的优先级级别来处理元素。

示例

 
// Using arrays for implementing a priority queue
class PriorityQueue {
  constructor( ) {
    this.queue = [ ];
  }

  enqueue( element, priority ) {
    this.queue.push({ element, priority });
    this.queue.sort(( a, b ) => a.priority - b.priority );
  }

  dequeue() {
    if ( this.isEmpty( ) ) {
      return " Queue is empty ";
    }
    Return this.queue.shift().element;
  }

  isEmpty() {
    return this.queue.length === 0;
  }

  print() {
    console.log( this.queue );
  }
}

// Example usage
const pq = new PriorityQueue();
pq.enqueue(" Task 1 ", 3 );
pq.enqueue(" Task 2 ", 1 );
pq.enqueue(" Task 3 ", 2 );
pq.print(); // Output : [ { element : ' Task 2 ', priority : 1 }, { element : ' Task 3 ', priority : 2 }, { element : ' Task 1 ', priority : 3 } ]
console.log( pq.dequeue( ) ); // Output : Task 2   

说明

PriorityQueue 类： 定义了一个名为 PriorityQueue 的类，代表优先级队列数据结构。
构造函数： 在创建 PriorityQueue 类的实例时初始化一个空数组队列。
enqueue 方法： 添加带有优先级的元素到优先级队列。它接受两个参数：element（要添加的数据）和 priority（元素的优先级级别）。元素及其优先级被存储为队列数组中的一个对象。添加元素后，使用具有自定义比较函数 (a, b) => a.priority - b.priority 的 sort 方法，根据优先级级别对队列数组进行排序。这确保了优先级较高的元素排在优先级较低的元素之前。
dequeue 方法： 此方法从队列中删除并返回具有最高优先级的元素。它使用 isEmpty 方法检查队列是否为空。如果队列不为空，它使用 shift 方法从队列数组中删除第一个元素并返回其 element 属性。
isEmpty 方法： 此方法通过检查队列数组的长度是否为零来判断队列是否为空。如果队列为空，则返回 true；否则，返回 false。
print 方法： 将队列数组中的项输出到控制台。
示例用法： 此示例演示了如何通过创建实例（pq）并执行操作（例如，入队具有不同优先级的元素、打印队列中的项以及出队元素）来使用 PriorityQueue 类。在示例中，“任务 1”的优先级为 3，“任务 2”的优先级为 1，“任务 3”的优先级为 2。入队和打印后，将出队并打印（优先级最高）的“任务 2”到控制台。

此 JavaScript 中优先级队列的实现考虑了根据其优先级级别对元素进行有效管理。

JavaScript 中的实现

可以使用各种方法在 JavaScript 中实现优先级队列。一种常见的方法是使用数组或链表，并结合适当的算法来维护优先级顺序。此外，JavaScript 还提供了对使用 Map 或 Set 数据结构实现优先级队列的内置支持。

示例 1

代码

 
// Priority Queue using Min-Heap
class PriorityQueue {
    constructor() {
        this.heap = [];
    }

    // Add element to the queue with its priority
    enqueue(element, priority) {
        const newNode = { element, priority };
        this.heap.push(newNode);
        this.bubbleUp();
    }

    // Remove and return the element with the highest priority
    dequeue() {
        if (this.isEmpty()) return "Queue is empty";
        const minNode = this.heap[0];
        const lastNode = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = lastNode;
            this.bubbleDown();
        }
        return minNode.element;
    }

    // Rearrange the heap after adding an element
    bubbleUp() {
        let currentIndex = this.heap.length - 1;
        while (currentIndex > 0) {
            const parentIndex = Math.floor((currentIndex - 1) / 2);
            if (this.heap[parentIndex].priority <= this.heap[currentIndex].priority) break;
            [this.heap[ parentIndex ], this.heap[currentIndex]] = [this.heap[currentIndex], this.heap[parentIndex]];
            currentIndex = parentIndex;
        }
    }

    // Rearrange the heap after removing an element
    bubbleDown() {
        let currentIndex = 0;
        const length = this.heap.length;
        const currentNode = this.heap[0];
        while (true) {
            let leftChildIndex = 2 * currentIndex + 1;
            let rightChildIndex = 2 * currentIndex + 2;
            let leftChild, rightChild;
            let swap = null;

            if ( leftChildIndex < length ) {
                leftChild = this.heap[ leftChildIndex ];
                if ( leftChild.priority < currentNode.priority ) {
                    swap = leftChildIndex;
                }
            }
            if ( rightChildIndex < length ) {
                rightChild = this.heap[ rightChildIndex ];
                if (
                    ( swap === null && rightChild.priority < currentNode.priority ) ||
                    ( swap !== null && rightChild.priority < leftChild.priority )
                ) {
                    swap = rightChildIndex;
                }
            }
            if ( swap === null ) break;
            [ this.heap[ currentIndex ], this.heap[ swap ]] = [ this.heap [ swap ], this.heap [ currentIndex ]];
            currentIndex = swap;
        }
    }

    // Check if the queue is empty
    isEmpty() {
        return this.heap.length === 0;
    }

    // Print the queue elements
    print() {
        console.log( this.heap );
    }
}

// Example usage
const pq = new PriorityQueue( );
pq.enqueue( " Task 1 ", 3 );
pq.enqueue( " Task 2 ", 1 );
pq.enqueue( " Task 3 ",  2 );
pq.print(); 
console.log( pq.dequeue( ));    

输出

 
 [ { element : ' Task 2 ', priority : 1 }, { element : ' Task 3 ', priority : 2 }, { element : ' Task 1 ', priority : 3 } ]
Task 2

示例 2

代码<

 
 // Node class to represent individual elements in the priority queue
class Node {
    constructor( element, priority ) {
        this.element = element;
        this.priority = priority;
        this.next = null;
    }
}

// Priority Queue implementation using Linked List
class PriorityQueue {
    constructor() {
        this.front = null; // Points to the front of the queue
    }

    // Add element to the queue with its priority
    enqueue( element, priority ) {
        const newNode = new Node(element, priority);
        if ( !this.front || priority < this.front.priority ) {
            newNode.next = this.front;
            this.front = newNode;
        } else {
            let current = this.front;
            while ( current.next && current.next.priority <= priority ) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
    }

    // Remove and return the element with the highest priority
    dequeue() {
        if (this.isEmpty()) return " Queue is empty ";
        const dequeuedElement = this.front.element;
        this.front = this.front.next;
        return dequeuedElement;
    }

    // Check if the queue is empty
    isEmpty() {
        return !this.front;
    }

    // Print the queue elements
    print() {
        let current = this.front;
        const queueElements = [ ];
        while (current) {
            queueElements.push({ element : current.element, priority : current.priority });
            current = current.next;
        }
        console.log( queueElements );
    }
}

// Example usage
const pq = new PriorityQueue();
pq.enqueue(" Task 1 ", 3 );
pq.enqueue(" Task 2 ", 1 );
pq.enqueue(" Task 3 ", 2 );
pq.print();
console.log(pq.dequeue()); 

输出

 
[ { element : ' Task 2 ', priority : 1 }, { element : ' Task 3 ', priority : 2 }, { element : ' Task 1 ', priority : 3 } ]
Task 2

优先级队列的应用

优先级队列在操作系统、任务调度、网络算法等各个领域都有应用。在操作系统中，优先级队列用于根据优先级级别管理进程，确保高优先级任务首先执行。此外，在网络路由算法中，优先级队列有助于根据优先级管理数据包，确保有效的数据传输。

结论

优先级队列提供了一种高效管理数据的强大工具，特别是当需要根据优先级级别处理元素时。在 JavaScript 中，可以通过各种方法实现优先级队列，为开发人员提供了选择最适合其应用程序的方法的灵活性。

通过理解和利用优先级队列，开发人员可以提高其 JavaScript 应用程序的性能和灵活性。

下一个主题JS setInterval() 方法

← 上一个下一个 →

JavaScript 中的优先队列

引言

理解优先队列

说明

JavaScript 中的实现

示例 1

示例 2

优先级队列的应用

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

JavaScript 基础

JS 变量和数据类型

JS 控制语句

JavaScript 函数

JavaScript 对象

JS 高级函数

JS Promises & Async/Await

JavaScript DOM

JavaScript JSON 对象

JavaScript 验证

JavaScript Cookies

异常处理

JavaScript 集合

JavaScript 事件

JavaScript OOPs

JavaScript BOM

面试题

选择题

差异

JavaScript Map 方法

JavaScript Handler

JavaScript Number 方法

JavaScript Reflect

JavaScript Symbol

Symbol 属性

JavaScript Math 方法

JavaScript Date 方法

JavaScript DataView

JavaScript Object 方法

JavaScript Set 方法

JavaScript 字符串方法

JavaScript TypedArray 方法

JavaScript WeakMap 方法

JavaScript WeakSet 方法

JavaScript 数组方法

JavaScript RegExp 对象

JavaScript 附加内容

JavaScript 杂项

JavaScript 进阶

问题

Lodash

JavaScript 中的优先队列

引言

理解优先队列

说明

JavaScript 中的实现

示例 1

示例 2

优先级队列的应用

结论

相关帖子

JavaScript 可执行文件

Javascript Booklet

如何使用 JavaScript 多维数组

JavaScript Return 命令

Unshift JavaScript

JavaScript 动画库

JavaScript 中的二分查找

JavaScript Null

Golang 与 JavaScript 对比