Priority Queues

Introduction

A priority queue is an abstract data type similar to a regular queue or stack, but where each element has a "priority" associated with it. Elements are served based on their priority; the element with the highest priority is served first. If elements have the same priority, they are served in the order they arrived (FIFO). Priority queues can be implemented using various data structures, such as arrays, linked lists, heaps, and binary search trees.

Use Cases

Priority queues are widely used in many applications:

• Operating Systems: Scheduling processes based on their priority.
• Network Routing Protocols: Determining the best path for data packets.
• Graph Algorithms: Dijkstra's algorithm for finding the shortest path.
• Event-driven Simulation: Managing events that occur at different times.

Types of Priority Queues

1. Max-Priority Queue: The element with the highest priority is served first.
2. Min-Priority Queue: The element with the lowest priority is served first.

Implementations

1. Array Implementation

Overview

An array can be used to implement a priority queue, but it is not efficient for large datasets due to its linear time complexity for insertion and deletion operations.

Code Example

class PriorityQueueArray {
    constructor() {
        this.items = [];
    }

    enqueue(element) {
        let added = false;
        for (let i = 0; i < this.items.length; i++) {
            if (this.items[i].priority > element.priority) {
                this.items.splice(i, 0, element);
                added = true;
                break;
            }
        }
        if (!added) {
            this.items.push(element);
        }
    }

    dequeue() {
        return this.items.shift();
    }

    front() {
        return this.items[0];
    }

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

    size() {
        return this.items.length;
    }
}

class Element {
    constructor(element, priority) {
        this.element = element;
        this.priority = priority;
    }
}

2. Linked List Implementation

Overview

A linked list can also be used to implement a priority queue. It provides better performance for insertion and deletion compared to arrays.

Code Example

class Node {
    constructor(element, priority) {
        this.element = element;
        this.priority = priority;
        this.next = null;
    }
}

class PriorityQueueLinkedList {
    constructor() {
        this.head = null;
    }

    enqueue(element, priority) {
        const newNode = new Node(element, priority);
        let current;

        if (this.head === null || this.head.priority > priority) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            current = this.head;
            while (current.next !== null && current.next.priority <= priority) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
    }

    dequeue() {
        if (this.isEmpty()) return null;
        const removedNode = this.head;
        this.head = this.head.next;
        return removedNode.element;
    }

    front() {
        if (this.isEmpty()) return null;
        return this.head.element;
    }

    isEmpty() {
        return this.head === null;
    }

    size() {
        let count = 0;
        let current = this.head;
        while (current !== null) {
            count++;
            current = current.next;
        }
        return count;
    }
}

3. Heap Implementation

Overview

A heap is the most efficient way to implement a priority queue, providing logarithmic time complexity for insertion and deletion operations.

Code Example

class MinHeap {
    constructor() {
        this.heap = [];
    }

    insert(value) {
        this.heap.push(value);
        this.bubbleUp();
    }

    bubbleUp() {
        let index = this.heap.length - 1;
        const element = this.heap[index];

        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            let parent = this.heap[parentIndex];

            if (element >= parent) break;
            this.heap[index] = parent;
            index = parentIndex;
        }
        this.heap[index] = element;
    }

    extractMin() {
        const min = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.sinkDown();
        }
        return min;
    }

    sinkDown() {
        let index = 0;
        const length = this.heap.length;
        const element = this.heap[0];

        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;

            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (leftChild < element) {
                    swap = leftChildIndex;
                }
            }

            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if (
                    (swap === null && rightChild < element) ||
                    (swap !== null && rightChild < leftChild)
                ) {
                    swap = rightChildIndex;
                }
            }

            if (swap === null) break;
            this.heap[index] = this.heap[swap];
            index = swap;
        }
        this.heap[index] = element;
    }

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

    size() {
        return this.heap.length;
    }
}

Best Practices

1. Choose the Right Implementation: Use a heap for efficient operations, especially when dealing with large datasets.
2. Handle Edge Cases: Always check if the priority queue is empty before performing operations like dequeue or front.
3. Maintain Priority Consistency: Ensure that priorities are consistent and meaningful in your application context.

Conclusion

Priority queues are essential data structures for managing tasks based on their importance. By understanding different implementations and their trade-offs, you can choose the most appropriate one for your specific use case. Whether using arrays, linked lists, or heaps, priority queues provide a powerful mechanism to handle prioritized tasks efficiently.