Initialize queue
Mark source visited
Enqueue source

While queue not empty:
    size = queue.size()   # level size

    Repeat size times:
        node = dequeue
        process node

        For each neighbor:
            If not visited:
                mark visited
                enqueue neighbor

When to use

• Shortest path (unweighted graph)
• Tree level-order traversal
• Multi-source BFS

Time: O(V + E)

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);

            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Initialize empty deque

For i in 0 to n-1:

    Remove indices out of window
    While deque not empty AND
          arr[i] >= arr[deque.back]:
        remove back

    Add current index

    If i >= k-1:
        output arr[deque.front]

When to use

• Maximum/minimum in subarray of size k
• O(n) window optimization

Time: O(n)

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new LinkedList<>();
    int[] result = new int[nums.length - k + 1];
    int index = 0;

    for (int i = 0; i < nums.length; i++) {

        while (!deque.isEmpty() &&
               deque.peekFirst() < i - k + 1)
            deque.pollFirst();

        while (!deque.isEmpty() &&
               nums[deque.peekLast()] <= nums[i])
            deque.pollLast();

        deque.offerLast(i);

        if (i >= k - 1)
            result[index++] = nums[deque.peekFirst()];
    }
    return result;
}

Initialize heap

For each element:
    insert into heap

If size > k:
    remove top element

Return heap.top

When to use

• Top K elements
• Kth largest/smallest
• Dijkstra
• Scheduling

Time: O(n log k)

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

    for (int num : nums) {
        pq.offer(num);
        if (pq.size() > k)
            pq.poll();
    }
    return pq.peek();
}

MaxHeap = lower half
MinHeap = upper half

For each number:
    Insert into MaxHeap

    Move largest from MaxHeap to MinHeap

    If MinHeap size > MaxHeap size:
        Move smallest from MinHeap to MaxHeap

Median:
    If sizes equal:
        average of tops
    Else:
        top of MaxHeap

When to use

• Median in data stream
• Dynamic balancing problems

Time per insert: O(log n)

class MedianFinder {

    PriorityQueue<Integer> maxHeap; // lower half
    PriorityQueue<Integer> minHeap; // upper half

    public MedianFinder() {
        maxHeap = new PriorityQueue<>(
            Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());

        if (minHeap.size() > maxHeap.size())
            maxHeap.offer(minHeap.poll());
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size())
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        return maxHeap.peek();
    }
}