Priority Queue and Heap Explained — How They Work and When to Use Them

import java.util.Arrays;

public class MinHeapDemo {

    // A hand-rolled min-heap so you can see exactly what's happening
    static int[] heapArray = new int[10];
    static int heapSize = 0;

    // Insert a value and restore the heap property by bubbling UP
    static void insert(int value) {
        if (heapSize == heapArray.length) {
            throw new IllegalStateException("Heap is full");
        }

        // Place the new value at the next available slot (end of array)
        heapArray[heapSize] = value;
        int insertedIndex = heapSize;
        heapSize++;

        // Bubble up: keep swapping with parent while we're smaller than it
        while (insertedIndex > 0) {
            int parentIndex = (insertedIndex - 1) / 2;

            if (heapArray[insertedIndex] < heapArray[parentIndex]) {
                // We're smaller than our parent — swap to fix heap property
                int temp = heapArray[insertedIndex];
                heapArray[insertedIndex] = heapArray[parentIndex];
                heapArray[parentIndex] = temp;

                insertedIndex = parentIndex; // move up and check again
            } else {
                break; // heap property is already satisfied
            }
        }
    }

    // Remove and return the minimum (root) element, then restore the heap
    static int extractMin() {
        if (heapSize == 0) throw new IllegalStateException("Heap is empty");

        int minValue = heapArray[0]; // root is always the minimum

        // Move the last element to the root — now we need to sink it down
        heapArray[0] = heapArray[heapSize - 1];
        heapSize--;

        // Sink down: swap with the smaller child until heap property is restored
        int currentIndex = 0;
        while (true) {
            int leftChild  = 2 * currentIndex + 1;
            int rightChild = 2 * currentIndex + 2;
            int smallest   = currentIndex;

            if (leftChild < heapSize && heapArray[leftChild] < heapArray[smallest]) {
                smallest = leftChild;
            }
            if (rightChild < heapSize && heapArray[rightChild] < heapArray[smallest]) {
                smallest = rightChild;
            }

            if (smallest == currentIndex) break; // we're already in the right spot

            // Swap current with the smallest child
            int temp = heapArray[currentIndex];
            heapArray[currentIndex] = heapArray[smallest];
            heapArray[smallest] = temp;

            currentIndex = smallest;
        }

        return minValue;
    }

    public static void main(String[] args) {
        int[] valuesToInsert = {40, 10, 30, 5, 20, 15};

        System.out.println("Inserting values: " + Arrays.toString(valuesToInsert));
        for (int value : valuesToInsert) {
            insert(value);
            System.out.println("  After inserting " + value + ": "
                + Arrays.toString(Arrays.copyOf(heapArray, heapSize)));
        }

        System.out.println("\nExtracting elements in priority order (smallest first):");
        while (heapSize > 0) {
            System.out.println("  Extracted min: " + extractMin());
        }
    }
}

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

public class TaskScheduler {

    // A task with a name and an urgency level (higher number = more urgent)
    static class Task {
        String name;
        int    urgencyLevel;

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

        @Override
        public String toString() {
            return name + " (urgency: " + urgencyLevel + ")";
        }
    }

    public static void main(String[] args) {

        // --- EXAMPLE 1: Min-heap (default) with integers ---
        System.out.println("=== Default Min-Heap ===");
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(50);
        minHeap.add(10);
        minHeap.add(30);
        minHeap.add(20);

        // poll() always removes the smallest element
        while (!minHeap.isEmpty()) {
            System.out.println("Processing ticket #" + minHeap.poll());
        }

        // --- EXAMPLE 2: Max-heap using reverseOrder ---
        System.out.println("\n=== Max-Heap with reverseOrder ===");
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.add(50);
        maxHeap.add(10);
        maxHeap.add(30);
        maxHeap.add(20);

        while (!maxHeap.isEmpty()) {
            System.out.println("Highest score: " + maxHeap.poll());
        }

        // --- EXAMPLE 3: Custom object heap — most urgent task first ---
        System.out.println("\n=== Custom Task Scheduler (most urgent first) ===");

        // Comparator: higher urgencyLevel comes out first (max-heap on urgency)
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(
            Comparator.comparingInt((Task t) -> t.urgencyLevel).reversed()
        );

        taskQueue.add(new Task("Update README",          1));
        taskQueue.add(new Task("Fix production bug",     10));
        taskQueue.add(new Task("Code review",            4));
        taskQueue.add(new Task("Deploy hotfix",          9));
        taskQueue.add(new Task("Write unit tests",       3));

        System.out.println("Tasks executed in priority order:");
        while (!taskQueue.isEmpty()) {
            System.out.println("  Executing: " + taskQueue.poll());
        }

        // --- EXAMPLE 4: Top-K pattern — find 3 largest salaries from a stream ---
        System.out.println("\n=== Top-3 Salaries from Salary Stream ===");
        int[] salaryStream = {45000, 92000, 67000, 110000, 38000, 88000, 75000, 120000};
        int topK = 3;

        // Min-heap of size K — the root is always the smallest of the top-K
        PriorityQueue<Integer> topSalaries = new PriorityQueue<>();

        for (int salary : salaryStream) {
            topSalaries.add(salary);

            // If we have more than K elements, evict the smallest
            // (it can't be in the top-K anymore)
            if (topSalaries.size() > topK) {
                topSalaries.poll(); // removes the current minimum
            }
        }

        System.out.println("Top " + topK + " salaries (ascending from heap):");
        while (!topSalaries.isEmpty()) {
            System.out.println("  $" + topSalaries.poll());
        }
    }
}

import java.util.*;

public class DijkstraShortestPath {

    // Represents a weighted directed edge in the graph
    static class Edge {
        int destinationNode;
        int travelCost;

        Edge(int destinationNode, int travelCost) {
            this.destinationNode = destinationNode;
            this.travelCost      = travelCost;
        }
    }

    // Represents a node and its current best-known distance from the source
    static class NodeDistance implements Comparable<NodeDistance> {
        int node;
        int distanceFromSource;

        NodeDistance(int node, int distanceFromSource) {
            this.node               = node;
            this.distanceFromSource = distanceFromSource;
        }

        @Override
        public int compareTo(NodeDistance other) {
            // Min-heap: the node with the SMALLEST distance gets popped first
            return Integer.compare(this.distanceFromSource, other.distanceFromSource);
        }
    }

    static int[] dijkstra(List<List<Edge>> graph, int sourceNode, int totalNodes) {
        // Initialize all distances as infinity (unreachable)
        int[] shortestDistance = new int[totalNodes];
        Arrays.fill(shortestDistance, Integer.MAX_VALUE);
        shortestDistance[sourceNode] = 0; // distance from source to itself is 0

        // Min-heap: always processes the closest unvisited node next
        PriorityQueue<NodeDistance> minHeap = new PriorityQueue<>();
        minHeap.add(new NodeDistance(sourceNode, 0));

        while (!minHeap.isEmpty()) {
            NodeDistance current = minHeap.poll();

            int currentNode     = current.node;
            int currentDistance = current.distanceFromSource;

            // Skip stale entries — we already found a better path to this node
            if (currentDistance > shortestDistance[currentNode]) {
                continue; // this is the "lazy deletion" workaround for no decrease-key
            }

            // Explore every neighbour of the current node
            for (Edge edge : graph.get(currentNode)) {
                int newDistance = shortestDistance[currentNode] + edge.travelCost;

                // Only update if we found a shorter path than previously known
                if (newDistance < shortestDistance[edge.destinationNode]) {
                    shortestDistance[edge.destinationNode] = newDistance;
                    // Push the improved distance into the heap
                    minHeap.add(new NodeDistance(edge.destinationNode, newDistance));
                }
            }
        }

        return shortestDistance;
    }

    public static void main(String[] args) {
        /*
         * Graph (city road network):
         *
         *  City 0 --4--> City 1
         *  City 0 --1--> City 2
         *  City 2 --2--> City 1
         *  City 1 --1--> City 3
         *  City 2 --5--> City 3
         *
         * Shortest from City 0:
         *   to City 1: 0 -> 2 -> 1 = 3  (not 0->1 directly = 4)
         *   to City 2: 0 -> 2       = 1
         *   to City 3: 0 -> 2 -> 1 -> 3 = 4
         */
        int totalNodes = 4;
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < totalNodes; i++) {
            graph.add(new ArrayList<>());
        }

        // Add directed edges (source -> destination, cost)
        graph.get(0).add(new Edge(1, 4));
        graph.get(0).add(new Edge(2, 1));
        graph.get(2).add(new Edge(1, 2));
        graph.get(1).add(new Edge(3, 1));
        graph.get(2).add(new Edge(3, 5));

        int sourceCity = 0;
        int[] distances = dijkstra(graph, sourceCity, totalNodes);

        System.out.println("Shortest distances from City " + sourceCity + ":");
        String[] cityNames = {"City 0 (Start)", "City 1", "City 2", "City 3"};
        for (int i = 0; i < totalNodes; i++) {
            System.out.println("  To " + cityNames[i] + ": " + distances[i] + " km");
        }
    }
}