DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Priority Queue

What Is a Priority Queue?

A priority queue is a data structure where each element has an associated priority. Elements are removed in priority order — the element with the highest (or lowest) priority is always dequeued first, regardless of insertion order.

Regular Queue (FIFO):     insertion order preserved
  Enqueue: 5, 3, 8, 1
  Dequeue: 5 → 3 → 8 → 1   (first in, first out)

Priority Queue (min):     smallest removed first
  Enqueue: 5, 3, 8, 1
  Dequeue: 1 → 3 → 5 → 8   (by value, not insertion order)

Priority Queue (max):     largest removed first
  Enqueue: 5, 3, 8, 1
  Dequeue: 8 → 5 → 3 → 1

The most common implementation is a binary heap — a complete binary tree stored as an array that maintains the heap property: every parent is ≤ (min-heap) or ≥ (max-heap) both its children.

Binary Heap Internals

Array Representation

A complete binary tree maps perfectly to an array. No pointers needed — the parent-child relationship is computed arithmetically.

Min-heap as a tree:           Same heap as an array:
         1                    index: 0  1  2  3  4  5  6
       /   \                  value: 1  3  2  9  5  8  7
      3     2
    /  \   / \
   9    5 8   7

Index arithmetic (0-based):
  Parent of i:       (i - 1) / 2
  Left child of i:   2 * i + 1
  Right child of i:  2 * i + 2

Verification:
  Node at index 1 (value 3): left child = 2*1+1=3 (value 9) ✓
                              right child = 2*1+2=4 (value 5) ✓
  Node at index 4 (value 5): parent = (4-1)/2=1 (value 3) ✓

Heap Property

MIN-HEAP: every parent ≤ both children
  The minimum element is always at index 0 (the root).
  poll() always returns the minimum.

MAX-HEAP: every parent ≥ both children
  The maximum element is always at index 0 (the root).
  poll() always returns the maximum.

Sift-Up (after insert)

When a new element is added, it goes to the end of the array and bubbles up until the heap property is restored.

Min-heap: [1, 3, 2, 9, 5, 8, 7] — insert 0

Add 0 at end:  [1, 3, 2, 9, 5, 8, 7, 0]   index=7
Parent of 7:   (7-1)/2 = 3 → value 9.  0 < 9 → SWAP
               [1, 3, 2, 0, 5, 8, 7, 9]   index=3
Parent of 3:   (3-1)/2 = 1 → value 3.  0 < 3 → SWAP
               [1, 0, 2, 3, 5, 8, 7, 9]   index=1
Parent of 1:   (1-1)/2 = 0 → value 1.  0 < 1 → SWAP
               [0, 1, 2, 3, 5, 8, 7, 9]   index=0
Root reached → STOP

Result: [0, 1, 2, 3, 5, 8, 7, 9]   min = 0 ✓

Sift-Down (after remove-min)

When the minimum is removed, the last element fills the root and sinks down until the heap property is restored.

Min-heap: [1, 3, 2, 9, 5, 8, 7] — remove min (1)

Move last to root: [7, 3, 2, 9, 5, 8]  (7 now at index 0)
Sift down:
  Children of 0: left=index 1 (3), right=index 2 (2). Min child=2 at idx 2.
  7 > 2 → SWAP   [2, 3, 7, 9, 5, 8]  (7 now at index 2)
  Children of 2: left=index 5 (8), right=index 6 (out of bounds).
  7 < 8 → STOP

Result: [2, 3, 7, 9, 5, 8]   returns 1, new min = 2 ✓

Complete Heap Implementation

Java

import java.util.ArrayList;
import java.util.NoSuchElementException;

public class MinHeap {

    private ArrayList<Integer> data;

    public MinHeap() {
        data = new ArrayList<>();
    }

    private int parent(int i) { return (i - 1) / 2; }
    private int left(int i)   { return 2 * i + 1; }
    private int right(int i)  { return 2 * i + 2; }

    private void swap(int i, int j) {
        int tmp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, tmp);
    }

    // INSERT — O(log n)
    public void insert(int value) {
        data.add(value);         // Add at end
        siftUp(data.size() - 1); // Restore heap property
    }

    private void siftUp(int i) {
        while (i > 0 && data.get(parent(i)) > data.get(i)) {
            swap(i, parent(i));
            i = parent(i);
        }
    }

    // PEEK MIN — O(1)
    public int peekMin() {
        if (isEmpty()) throw new NoSuchElementException("Heap is empty");
        return data.get(0);
    }

    // REMOVE MIN — O(log n)
    public int removeMin() {
        if (isEmpty()) throw new NoSuchElementException("Heap is empty");
        int min = data.get(0);

        // Move last element to root and remove the last slot
        int last = data.size() - 1;
        data.set(0, data.get(last));
        data.remove(last);

        if (!isEmpty()) siftDown(0);  // Restore heap property
        return min;
    }

    private void siftDown(int i) {
        int n = data.size();
        while (true) {
            int smallest = i;
            int l = left(i), r = right(i);

            if (l < n && data.get(l) < data.get(smallest)) smallest = l;
            if (r < n && data.get(r) < data.get(smallest)) smallest = r;

            if (smallest == i) break;  // Heap property satisfied
            swap(i, smallest);
            i = smallest;
        }
    }

    public boolean isEmpty() { return data.isEmpty(); }
    public int     size()    { return data.size(); }

    // BUILD HEAP from array — O(n)
    public static MinHeap buildHeap(int[] arr) {
        MinHeap heap = new MinHeap();
        for (int v : arr) heap.data.add(v);

        // Sift down all non-leaf nodes from bottom up
        for (int i = (arr.length / 2) - 1; i >= 0; i--) {
            heap.siftDown(i);
        }
        return heap;
    }

    @Override
    public String toString() { return "MinHeap: " + data; }

    public static void main(String[] args) {
        MinHeap heap = new MinHeap();

        heap.insert(5); heap.insert(3); heap.insert(8);
        heap.insert(1); heap.insert(7);
        System.out.println(heap);                      // [1, 3, 8, 5, 7]
        System.out.println("Min: " + heap.peekMin());  // 1
        System.out.println("Remove: " + heap.removeMin()); // 1
        System.out.println("Remove: " + heap.removeMin()); // 3
        System.out.println(heap);                      // [5, 7, 8]

        // Build heap
        MinHeap built = MinHeap.buildHeap(new int[]{4, 10, 3, 5, 1});
        System.out.println("Built: " + built);         // [1, 4, 3, 5, 10]
    }
}

Output:
MinHeap: [1, 3, 8, 5, 7]
Min: 1
Remove: 1
Remove: 3
MinHeap: [5, 7, 8]
Built: [1, 4, 3, 5, 10]

Built-in Priority Queues

Java

import java.util.*;

public class BuiltinPQ {

    public static void main(String[] args) {
        // ── MIN-HEAP (default) ────────────────────────────────────
        PriorityQueue<Integer> minPQ = new PriorityQueue<>();
        minPQ.offer(5); minPQ.offer(3); minPQ.offer(8); minPQ.offer(1);

        System.out.println("Min peek:   " + minPQ.peek());    // 1
        System.out.println("Min poll:   " + minPQ.poll());    // 1
        System.out.println("Min poll:   " + minPQ.poll());    // 3

        // ── MAX-HEAP ──────────────────────────────────────────────
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
        maxPQ.offer(5); maxPQ.offer(3); maxPQ.offer(8); maxPQ.offer(1);

        System.out.println("Max peek:   " + maxPQ.peek());    // 8
        System.out.println("Max poll:   " + maxPQ.poll());    // 8
        System.out.println("Max poll:   " + maxPQ.poll());    // 5

        // ── CUSTOM COMPARATOR (sort by string length) ─────────────
        PriorityQueue<String> strPQ = new PriorityQueue<>(
            Comparator.comparingInt(String::length)
        );
        strPQ.offer("banana"); strPQ.offer("fig"); strPQ.offer("kiwi");

        System.out.println("Shortest:   " + strPQ.poll());   // fig (len 3)
        System.out.println("Next:       " + strPQ.poll());   // kiwi (len 4)

        // ── WITH PAIRS [value, index] ─────────────────────────────
        PriorityQueue<int[]> pairPQ = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[0])
        );
        pairPQ.offer(new int[]{3, 0});
        pairPQ.offer(new int[]{1, 2});
        pairPQ.offer(new int[]{2, 1});

        int[] top = pairPQ.poll();
        System.out.println("Min pair: [" + top[0] + "," + top[1] + "]"); // [1,2]
    }
}

Output (Java):
Min peek:   1
Min poll:   1
Min poll:   3
Max peek:   8
Max poll:   8
Max poll:   5
Shortest:   fig
Min pair:   [1, 2]

Application 1: K-th Largest Element

Problem: Find the k-th largest element in an unsorted array.

Approach: Maintain a min-heap of size k. For each element: push to heap. If heap grows beyond k, pop the minimum. After processing all elements, the heap top is the k-th largest.

Why min-heap of size k?
  The heap holds the k largest elements seen so far.
  The smallest of those k elements is at the top.
  That minimum is the k-th largest overall.

nums = [3,2,1,5,6,4],  k=2

Process 3: heap=[3]
Process 2: heap=[2,3]  (size=k=2 — full)
Process 1: push 1→[1,3,2], pop min=1→[2,3]   (1 < heap min=2? no wait...)
  Actually: push 1: heap=[1,2,3]. Size>k → pop min (1). heap=[2,3]
Process 5: push 5: heap=[2,3,5]. Size>k → pop min (2). heap=[3,5]
Process 6: push 6: heap=[3,5,6]. Size>k → pop min (3). heap=[5,6]
Process 4: push 4: heap=[4,5,6]. Size>k → pop min (4). heap=[5,6]

heap top = 5 = 2nd largest ✓

Java

import java.util.PriorityQueue;

public class KthLargest {

    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();   // Remove the smallest — keep only k largest
            }
        }

        return minHeap.peek();   // Top of min-heap = k-th largest
    }

    public static void main(String[] args) {
        System.out.println(findKthLargest(new int[]{3,2,1,5,6,4}, 2));   // 5
        System.out.println(findKthLargest(new int[]{3,2,3,1,2,4,5,5,6}, 4)); // 4
        System.out.println(findKthLargest(new int[]{1}, 1));              // 1
    }
}

Output:
5
4
1

Application 2: Merge K Sorted Lists

Problem: Merge k sorted linked lists into one sorted list.

Approach: Use a min-heap. Start by pushing the head of each list. Pop the minimum node, add to result, then push that node's next (if it exists).

Java

import java.util.PriorityQueue;

public class MergeKSorted {

    static class ListNode {
        int val; ListNode next;
        ListNode(int v) { val = v; next = null; }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minPQ = new PriorityQueue<>(
            (a, b) -> a.val - b.val   // Min-heap by node value
        );

        // Push head of each list
        for (ListNode node : lists) {
            if (node != null) minPQ.offer(node);
        }

        ListNode dummy = new ListNode(0), curr = dummy;

        while (!minPQ.isEmpty()) {
            ListNode min = minPQ.poll();   // Get globally smallest
            curr.next = min;
            curr      = curr.next;

            if (min.next != null) minPQ.offer(min.next);  // Push next from same list
        }

        return dummy.next;
    }

    public static void main(String[] args) {
        // [1→4→5], [1→3→4], [2→6]  →  [1→1→2→3→4→4→5→6]
        ListNode l1 = new ListNode(1); l1.next = new ListNode(4); l1.next.next = new ListNode(5);
        ListNode l2 = new ListNode(1); l2.next = new ListNode(3); l2.next.next = new ListNode(4);
        ListNode l3 = new ListNode(2); l3.next = new ListNode(6);

        ListNode result = mergeKLists(new ListNode[]{l1, l2, l3});
        StringBuilder sb = new StringBuilder();
        while (result != null) { sb.append(result.val).append("→"); result = result.next; }
        System.out.println(sb.toString().replaceAll("→$", ""));  // 1→1→2→3→4→4→5→6
    }
}

Output:
1→1→2→3→4→4→5→6

Application 3: Dijkstra's Shortest Path

Problem: Find the shortest path from a source node to all other nodes in a weighted graph.

Why priority queue: Always process the unvisited node with the smallest known distance first — a greedy strategy that only works because of the min-heap's O(log n) extraction.

Java

import java.util.*;

public class Dijkstra {

    public static int[] dijkstra(int[][] graph, int source) {
        int   n    = graph.length;
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        // Min-heap: [distance, node]
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, source});

        while (!pq.isEmpty()) {
            int[] curr     = pq.poll();
            int   currDist = curr[0], u = curr[1];

            if (currDist > dist[u]) continue;  // Stale entry — skip

            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0) {          // Edge exists
                    int newDist = dist[u] + graph[u][v];
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        pq.offer(new int[]{newDist, v});
                    }
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        //        0   1   2   3   4
        int[][] g = {
            {0, 4, 0, 0, 8},   // node 0 → 1 (4), 0 → 4 (8)
            {4, 0, 8, 0, 11},  // node 1 → 2 (8), 1 → 4 (11)
            {0, 8, 0, 7, 2},   // node 2 → 3 (7), 2 → 4 (2)
            {0, 0, 7, 0, 0},   // node 3 → 2 (7)
            {8, 11, 2, 0, 0}   // node 4 → 0 (8), 4 → 1 (11), 4 → 2 (2)
        };

        int[] dist = dijkstra(g, 0);
        System.out.println("Distances from node 0: " + Arrays.toString(dist));
        // [0, 4, 10, 17, 8]
    }
}

Output:
Distances from node 0: [0, 4, 10, 17, 8]

Build Heap O(n) vs Repeated Insert O(n log n)

Repeated insertion (n inserts, each O(log n)):
  Total: O(n log n)

Build heap (Floyd's algorithm — sift-down from n/2 to 0):
  Total: O(n) — provable by summing work at each level:
    Level h (height h from bottom): n/2^(h+1) nodes, each O(h) work
    Sum = Σ (n/2^h) × h for h=1..log n ≈ 2n = O(n)

When to use each:
  Build from existing array → buildHeap O(n)
  Insert elements one by one → repeated insert O(n log n)
  In Python: heapq.heapify(arr) uses Floyd's O(n)
  In Java:   new PriorityQueue(collection) uses O(n) internally

Complexity Summary

Operation	Binary Heap	Notes
insert / offer	O(log n)	Sift-up from leaf
remove min/max	O(log n)	Sift-down from root
peek min/max	O(1)	Root is always min/max
build from n elements	O(n)	Floyd's algorithm
search for arbitrary element	O(n)	Heap has no ordering on non-root
delete arbitrary element	O(log n)	Find O(n) + sift O(log n)
merge two heaps	O(n)	Concatenate + build

Common Mistakes

Java max-heap: using -a.compareTo(b) on Integer. For primitive int comparisons, use Collections.reverseOrder() or (a, b) -> b - a. Avoid (a, b) -> a.compareTo(b) reversed for potential Integer overflow with extreme values — b - a can overflow when a and b are near Integer.MIN_VALUE and Integer.MAX_VALUE. Use Integer.compare(b, a) for safety.

Python max-heap: forgetting to negate when popping. You push -val but must pop and negate the result: -heapq.heappop(heap). Failing to negate the popped value gives the wrong answer.

Dijkstra: not skipping stale heap entries. When a shorter path to node v is found, a new entry is pushed with the updated distance. The old entry (higher distance) remains in the heap — it must be discarded with if currDist > dist[u]: continue. Without this check, the algorithm processes nodes multiple times and may produce wrong results.

Using size() comparison wrong in k-th largest. The heap should maintain exactly k elements. Pop when heap.size() > k — after the push. Popping before the push discards elements prematurely.

Interview Questions

Q: When would you use a max-heap instead of a min-heap for a k-th largest problem?

For k-th largest you want the k largest elements at all times. A min-heap of size k achieves this: the minimum of those k elements is at the top — that is the k-th largest overall. A max-heap of size n would work but requires O(n log k) extra pops instead. For k-th smallest, use a max-heap of size k — the maximum of the k smallest is the k-th smallest.

Q: Why does Dijkstra's algorithm use a priority queue instead of a regular queue?

BFS with a regular queue finds the shortest path in terms of number of edges — it processes nodes level by level. Dijkstra processes the unvisited node with the smallest known distance first — a greedy strategy that requires sorting by distance. A priority queue gives O(log V) extraction of the minimum-distance node, giving total complexity O((V + E) log V). Without a priority queue, finding the minimum each time would be O(V), giving O(V²) total — acceptable for dense graphs but slower for sparse ones.

Q: What is the difference between a priority queue and a sorted array for implementing Dijkstra?

Both work. A sorted array gives O(1) peek but O(n) insert (maintain sorted order). A binary heap gives O(log n) for both insert and extract-min. For Dijkstra with V vertices and E edges: sorted array is O(V²) total, binary heap is O((V + E) log V). For dense graphs (E ≈ V²), the sorted array is comparable; for sparse graphs (E ≈ V), the heap wins significantly.

FAQs

Can a priority queue have elements with equal priority?

Yes. Ties in priority are broken arbitrarily — the heap does not guarantee FIFO ordering for equal priorities. Java's PriorityQueue makes no stability guarantee. Python's heapq breaks ties by comparing the second element if using tuples (priority, value) — if values are not comparable, use (priority, counter, value) where counter is a unique integer.

What is the difference between heapq.heappush + heappop and heapq.heappushpop in Python?

heappushpop(heap, item) pushes the new item then pops and returns the smallest — in one operation, and it is more efficient than separate push + pop. If the new item is smaller than the current minimum, it returns the item immediately without modifying the heap. Use it in the k-th largest pattern: heapq.heappushpop(heap, num) when len(heap) >= k.

Why is peek() O(1) but removal O(log n)?

peek() reads the root — array index 0 — one array access. The root is always the minimum (or maximum) by the heap property. Removal is O(log n) because after removing the root, the last element is placed at the root and sifted down — comparing with both children at each level of the tree, visiting at most O(log n) nodes.

Summary

A priority queue removes elements by priority, not arrival order. The binary heap provides O(log n) insert and remove, O(1) peek, and O(n) build-from-array.

Key mechanics:

›Array representation: parent at (i-1)/2, left child at 2i+1, right child at 2i+2
›Min-heap: every parent ≤ both children — root is always the minimum
›Max-heap: every parent ≥ both children — root is always the maximum
›Sift-up: after insert — bubble new element up until heap property holds
›Sift-down: after remove-root — sink last element down until heap property holds
›Build heap: O(n) using Floyd's algorithm (sift-down all non-leaves, bottom-up)

Built-in defaults:

›Java: PriorityQueue<E> is a min-heap; pass Collections.reverseOrder() for max-heap
›Python: heapq is always min-heap; negate values to simulate max-heap
›C++: priority_queue<T> is a max-heap by default; use greater<T> for min-heap

Core applications:

›K-th largest: min-heap of size k — top = k-th largest — O(n log k)
›Merge k sorted lists: min-heap of k list heads — O(n log k)
›Dijkstra's algorithm: min-heap of (distance, node) — O((V+E) log V)
›Top-K pattern: use opposite heap type — k-th largest needs min-heap, k-th smallest needs max-heap

In the next topic you will explore Queue in BFS — how the queue drives breadth-first search for shortest paths, level-order traversal, and the classic graph/tree BFS problems.

Suggested Quiz

A priority queue removes elements in what order?

1/6