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 dequeued based on their priority.

Min-Heap Implementation

Using Min-Heap

A min-heap is a binary tree where the parent node is less than or equal to its child nodes. It is commonly used to implement a priority queue where the smallest element is given the highest priority.


import java.util.PriorityQueue;

PriorityQueue minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.add(20);
minHeap.add(5);
System.out.println(minHeap.poll()); // Outputs: 5

Max-Heap Implementation

Using Max-Heap

A max-heap is a binary tree where the parent node is greater than or equal to its child nodes. It is used to implement a priority queue where the largest element is given the highest priority.


import java.util.Collections;
import java.util.PriorityQueue;

PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(10);
maxHeap.add(20);
maxHeap.add(5);
System.out.println(maxHeap.poll()); // Outputs: 20

Custom Comparator

Using Custom Comparator

A custom comparator can be used to define the order of elements in a priority queue. This allows for complex ordering beyond simple natural ordering.


import java.util.Comparator;
import java.util.PriorityQueue;

PriorityQueue pq = new PriorityQueue<>(new Comparator() {
    public int compare(String s1, String s2) {
        return s2.length() - s1.length(); // Longer strings have higher priority
    }
});
pq.add("short");
pq.add("medium");
pq.add("longest");
System.out.println(pq.poll()); // Outputs: longest

Priority Queue with Objects

Storing Custom Objects

Priority queues can store objects, and ordering can be defined based on any property of the object using a comparator.


class Task {
    String name;
    int priority;
    Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }
}

PriorityQueue taskQueue = new PriorityQueue<>(new Comparator() {
    public int compare(Task t1, Task t2) {
        return t1.priority - t2.priority; // Lower priority number has higher priority
    }
});
taskQueue.add(new Task("Task1", 3));
taskQueue.add(new Task("Task2", 1));
System.out.println(taskQueue.poll().name); // Outputs: Task2

Scheduling Tasks

Using Priority Queue for Scheduling

Priority queues are often used in scheduling tasks, where tasks with higher priority are executed first.


class Job implements Comparable {
    String jobName;
    int priority;
    Job(String jobName, int priority) {
        this.jobName = jobName;
        this.priority = priority;
    }
    public int compareTo(Job other) {
        return Integer.compare(this.priority, other.priority);
    }
}

PriorityQueue jobQueue = new PriorityQueue<>();
jobQueue.add(new Job("Job1", 2));
jobQueue.add(new Job("Job2", 1));
System.out.println(jobQueue.poll().jobName); // Outputs: Job2

Event Management

Managing Events with Priority Queue

In event-driven systems, priority queues can manage events based on their urgency, ensuring that critical events are handled first.


class Event {
    String description;
    int urgency;
    Event(String description, int urgency) {
        this.description = description;
        this.urgency = urgency;
    }
}

PriorityQueue eventQueue = new PriorityQueue<>(new Comparator() {
    public int compare(Event e1, Event e2) {
        return e2.urgency - e1.urgency; // Higher urgency comes first
    }
});
eventQueue.add(new Event("Low urgency event", 1));
eventQueue.add(new Event("High urgency event", 3));
System.out.println(eventQueue.poll().description); // Outputs: High urgency event

Network Packet Scheduling

Packet Scheduling in Networks

Priority queues are used in network routers to schedule packets for transmission based on priority levels, ensuring important packets are sent first.


class Packet {
    String data;
    int priority;
    Packet(String data, int priority) {
        this.data = data;
        this.priority = priority;
    }
}

PriorityQueue packetQueue = new PriorityQueue<>(new Comparator() {
    public int compare(Packet p1, Packet p2) {
        return p1.priority - p2.priority;
    }
});
packetQueue.add(new Packet("Packet1", 2));
packetQueue.add(new Packet("Packet2", 1));
System.out.println(packetQueue.poll().data); // Outputs: Packet2

Resource Management

Priority Queue in Resource Allocation

In resource management systems, priority queues help allocate resources to tasks based on priority, ensuring critical tasks receive resources first.


class ResourceRequest {
    String requestor;
    int priority;
    ResourceRequest(String requestor, int priority) {
        this.requestor = requestor;
        this.priority = priority;
    }
}

PriorityQueue resourceQueue = new PriorityQueue<>(new Comparator() {
    public int compare(ResourceRequest r1, ResourceRequest r2) {
        return r2.priority - r1.priority;
    }
});
resourceQueue.add(new ResourceRequest("User1", 1));
resourceQueue.add(new ResourceRequest("User2", 3));
System.out.println(resourceQueue.poll().requestor); // Outputs: User2

Emergency Services Dispatch

Dispatching Emergency Services

Priority queues are crucial in dispatching emergency services where incidents are prioritized based on severity, ensuring the most urgent cases are addressed first.


class EmergencyCall {
    String location;
    int severity;
    EmergencyCall(String location, int severity) {
        this.location = location;
        this.severity = severity;
    }
}

PriorityQueue emergencyQueue = new PriorityQueue<>(new Comparator() {
    public int compare(EmergencyCall e1, EmergencyCall e2) {
        return e2.severity - e1.severity;
    }
});
emergencyQueue.add(new EmergencyCall("Location1", 2));
emergencyQueue.add(new EmergencyCall("Location2", 5));
System.out.println(emergencyQueue.poll().location); // Outputs: Location2