Introduction to Heaps

Heaps are a specialized tree-based data structure that satisfies the heap property. They are particularly useful for implementing priority queues and are frequently encountered in algorithms and competitive programming problems. In essence, a heap maintains a partial ordering, which is weaker than a full sorting. This allows for efficient retrieval of the minimum or maximum element without completely sorting the entire dataset.

This document will cover the fundamentals of heaps, focusing on their properties, types (Min-Heap and Max-Heap), and Java implementations relevant to competitive programming.

Overview of Heaps: Properties and Comparison

Heap Properties

A heap is a complete binary tree that satisfies the heap property. "Complete" means that all levels are completely filled except possibly the last level, which is filled from left to right.

• Min-Heap: For every node i, the value of i is less than or equal to the value of its children. Therefore, the root node contains the smallest element in the heap.
• Max-Heap: For every node i, the value of i is greater than or equal to the value of its children. Therefore, the root node contains the largest element in the heap.

Heap Representation

Heaps are typically represented using arrays. This is an efficient representation because it allows for easy calculation of the parent and child indices:

• Parent of node at index i: (i - 1) / 2
• Left child of node at index i: 2 * i + 1
• Right child of node at index i: 2 * i + 2

Comparison with Other Data Structures

Heaps offer a different set of advantages compared to other data structures like sorted arrays, linked lists, and binary search trees.

• Sorted Array: Provides O(1) access to the minimum or maximum element but insertion and deletion are O(n) in the worst case.
• Linked List: Insertion and deletion are O(1) (if you have a pointer to the node), but finding the minimum or maximum is O(n).
• Binary Search Tree (BST): Insertion, deletion, and search are typically O(log n) on average, but can degrade to O(n) in the worst case (e.g., a skewed tree).
• Heap: Provides O(1) access to the minimum or maximum element (root node). Insertion and deletion (specifically, removing the root and heapifying) are O(log n).

Heaps excel when you frequently need to access the minimum or maximum element and perform insertions and deletions. Their logarithmic time complexity for these operations makes them suitable for priority queue implementations and certain graph algorithms.

Understanding Min-Heap and Max-Heap

Min-Heap

A Min-Heap is a heap where the value of each node is less than or equal to the value of its children. The smallest element is always at the root.

Min-Heap Operations

• Insert: Add a new element to the end of the array representing the heap and then "heapify up" (bubble up) the element to maintain the heap property.
• Extract Min: Remove the root element (minimum value), replace it with the last element in the array, reduce the heap size by one, and then "heapify down" (bubble down) the new root to maintain the heap property.
• Peek Min: Return the root element (minimum value) without removing it.

Java Min-Heap Implementation

 import java.util.PriorityQueue;

public class MinHeap {

    public static void main(String[] args) {
        // Using PriorityQueue (which is a Min-Heap by default)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        minHeap.add(5);
        minHeap.add(1);
        minHeap.add(9);
        minHeap.add(3);

        System.out.println("Min element: " + minHeap.peek()); // Output: 1

        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " "); // Output: 1 3 5 9
        }
        System.out.println();
    }
} 

Max-Heap

A Max-Heap is a heap where the value of each node is greater than or equal to the value of its children. The largest element is always at the root.

Max-Heap Operations

• Insert: Add a new element to the end of the array representing the heap and then "heapify up" (bubble up) the element to maintain the heap property.
• Extract Max: Remove the root element (maximum value), replace it with the last element in the array, reduce the heap size by one, and then "heapify down" (bubble down) the new root to maintain the heap property.
• Peek Max: Return the root element (maximum value) without removing it.

Java Max-Heap Implementation

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

public class MaxHeap {

    public static void main(String[] args) {
        // Using PriorityQueue with Collections.reverseOrder() for Max-Heap
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        maxHeap.add(5);
        maxHeap.add(1);
        maxHeap.add(9);
        maxHeap.add(3);

        System.out.println("Max element: " + maxHeap.peek()); // Output: 9

        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " "); // Output: 9 5 3 1
        }
        System.out.println();
    }
} 

Heaps in Competitive Programming

Heaps are frequently used in competitive programming for a variety of tasks, including:

• Priority Queues: Implementing custom priority queues based on specific criteria. The PriorityQueue class in Java is generally used for this.
• Heap Sort: An efficient sorting algorithm with O(n log n) time complexity.
• Graph Algorithms: Algorithms like Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm rely heavily on priority queues, which are often implemented using heaps.
• Finding the k-th Largest/Smallest Element: Heaps can efficiently find the k-th largest or smallest element in an array.

Example Problem: Finding the Kth Largest Element

Given an array of integers and an integer k, find the kth largest element in the array.

Solution using Max-Heap

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

public class KthLargest {

    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (int num : nums) {
            maxHeap.add(num);
        }

        for (int i = 1; i < k; i++) {
            maxHeap.poll();
        }

        return maxHeap.peek();
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int kthLargest = findKthLargest(nums, k);
        System.out.println("The " + k + "th largest element is: " + kthLargest); // Output: 5
    }
} 

Solution using Min-Heap (Optimized)

 import java.util.PriorityQueue;


public class KthLargestOptimized {

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

        for (int num : nums) {
            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // Remove the smallest element if size exceeds k
            }
        }

        return minHeap.peek(); // The root is now the kth largest
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int kthLargest = findKthLargest(nums, k);
        System.out.println("The " + k + "th largest element is: " + kthLargest); // Output: 5
    }
} 

The optimized solution with Min-Heap is often preferred for its space efficiency, especially when dealing with very large arrays. It only stores `k` elements at any given time.