Implementing Priority Queue in JavaScript

1. Introduction to priority queue

We know that when an element is inserted into an ordinary queue, the data will be placed at the back end, and the previous data will not be processed until all the previous elements are processed. However, the priority queue considers the priority of the data when inserting an element and compares it with the priority of other data. After the comparison is completed, the correct position of this element in the queue can be obtained. The other processing methods are basically the same as those of the basic queue.

The main issues to consider for priority queues are:

• Each element is no longer just a piece of data, but also contains the priority of the data;
• In the add method, put in the correct position according to the priority.

There are also examples of priority queues used in daily life, such as hospital (emergency department) waiting rooms. Doctors will give priority to patients with more serious conditions. In computers, we can also use priority queues to rearrange the order of tasks in the queue. For example, the importance of tasks processed by each thread is different, and we can use the size of the priority to determine the order in which the thread is processed in the queue.

2. Priority Queue Encapsulation

The operation of the priority queue is basically the same as that of the queue, but the insertion operation is different, so here we mainly implement the insertion operation of the priority queue.

For example, if we want to insert elements according to the priority of certain data, we first create a class to encapsulate the priority queue, create a constructor inside it to save the priority and data of the element, and then add an attribute to store the element.

The code is as follows:

function PtiorityQueue(){
            var items = [];
            //Encapsulate a new constructor to save elements and their priorities function queueElement(element,priority){
                this.element = element;
                this.priority = priority;
            }
        }

After the creation is completed, the insertion operation is implemented:

• If there is no element in the queue, insert it directly
• If the priority of the element to be inserted is less than the priority of the element inside the queue, it is inserted after sorting.

The specific implementation code is as follows:

function PtiorityQueue(){
   this.items = [];
    //Encapsulate a new constructor to save elements and their priorities function QueueElement(element,priority){
        this.element = element;
        this.priority = priority;
    }
     //1. Implement the insertion method PtiorityQueue.prototype.enqueue = function(element,priority){
        //1. Create queueElement object var queueElement = new QueueElement(element,priority);
        //2. Determine whether the queue is empty if (this.items.length == 0) {
            this.items.push(queueElement);
        }else{
            var flag = false;
            for(var i =0;i<this.items.length;i++){
                if (queueElement.priority < this.items[i].priority) {
                    this.items.splice(i,0,queueElement);
                    flag = true;
                    break;
                }
            }
            if(!flag){
                this.items.push(queueElement)
            }
        }
     }
}

The input test data is:

var pq = new PtiorityQueue();
pq.enqueue('d',30)
pq.enqueue('c',50)
pq.enqueue('a',100)
pq.enqueue('b',60)
pq.enqueue('e',20)
console.log(pq);

The print result is:

This is the end of this article about implementing priority queues in JavaScript. For more information about priority queues, please search for previous articles on 123WORDPRESS.COM or continue to browse the following related articles. I hope you will support 123WORDPRESS.COM in the future!