Priority Queue

Explore the ins and outs of Priority Queue data structure in our latest blog post. From understanding the fundamentals to advanced techniques, discover how to leverage priority queue for optimal efficiency in your coding projects.

Introduction

A Priority Queue is a specialized data structure that stores elements along with their associated priorities, allowing for efficient retrieval of the highest-priority element. Unlike a regular queue, where elements are processed in a first-in-first-out (FIFO) manner, a Priority Queue retrieves elements based on their priority, ensuring that the highest-priority element is processed first.

The priority of an element can be determined by a comparison function or a key associated with the element. Elements with higher priority values are considered more urgent or important and are retrieved before elements with lower priority values.

Priority Queues find applications in various domains, including task scheduling, network routing, and graph algorithms. They offer a flexible and efficient way to manage tasks and resources based on their relative priorities, contributing to optimized solutions in algorithm design and system management.

In summary, a Priority Queue is a fundamental data structure that enhances the efficiency of processing tasks by prioritizing elements based on their importance or urgency.

Available Operations

1. Enqueue (Insertion): Adds an element to the Priority Queue with its associated priority.
2. Dequeue (Removal): Removes and returns the highest-priority element from the Priority Queue.
3. Peek (Access): Retrieves the highest-priority element from the Priority Queue without removing it.
4. Size (Count): Returns the number of elements currently stored in the Priority Queue.
5. IsEmpty: Checks if the Priority Queue is empty.

Implementation

class PriorityQueue<T> {
    private elements: T[];
    private compare: (a: T, b: T) => number;
 
    constructor(compare: (a: T, b: T) => number) {
        this.elements = [];
        this.compare = compare;
    }
 
    enqueue(item: T): void {
        this.elements.push(item);
        this.elements.sort((a, b) => this.compare(a, b));
    }
 
    dequeue(): T | undefined {
        return this.elements.shift();
    }
 
    peek(): T | undefined {
        return this.elements[0];
    }
 
    size(): number {
        return this.elements.length;
    }
 
    isEmpty(): boolean {
        return this.elements.length === 0;
    }
}

Usage

 
// Define a compare function for numbers
const compareNumbers = (a: number, b: number) => a - b;
 
// Create a priority queue for numbers
const pq = new PriorityQueue<number>(compareNumbers);
 
// Enqueue some numbers
pq.enqueue(5);
pq.enqueue(2);
pq.enqueue(8);
 
// Dequeue elements (sorted order because of priority queue)
console.log(pq.dequeue()); // Output: 2
console.log(pq.dequeue()); // Output: 5
console.log(pq.dequeue()); // Output: 8