Heap Data Structure: Min Heap, Max Heap, and Priority Queue

A Heap is a complete binary tree-based data structure that satisfies a specific ordering property between parent and child nodes. It is commonly used when an application needs quick access to the smallest or largest element.

There are two primary types of binary heaps: Min Heap and Max Heap. In a Min Heap, the smallest element is stored at the root, while in a Max Heap, the largest element is stored at the root.

Heaps are widely used to implement Priority Queues and are important in algorithms such as Heap Sort, Dijkstra's shortest path algorithm, and several Top-K problems.

1. Heap Structure and Properties

A binary heap must satisfy two important properties: the complete binary tree property and the heap-order property.

Complete Binary Tree: Every level is completely filled except possibly the last level, which is filled from left to right.
Heap Property: Every parent node maintains an ordering relationship with its children.
Root Element: The root contains the minimum value in a Min Heap or the maximum value in a Max Heap.
Array Representation: A binary heap can be efficiently stored in a one-dimensional array without requiring explicit tree nodes.

For a zero-based array representation, the children of a node at index i are located at 2 × i + 1 and 2 × i + 2, while its parent is located at (i - 1) / 2.

2. Min Heap vs Max Heap

Min Heap

In a Min Heap, every parent node is less than or equal to its children. Therefore, the smallest element is always available at the root.

Max Heap

In a Max Heap, every parent node is greater than or equal to its children. Therefore, the largest element is always available at the root.

3. Core Heap Operations

1. Insert

To insert an element, place it at the next available position to preserve the complete binary tree property. Then repeatedly compare it with its parent and move it upward until the heap property is restored. This process is called heapify-up or sift-up.

Time Complexity: O(log N)

2. Peek

The root element can be accessed directly without removing it. In a Min Heap, peek returns the minimum element, while in a Max Heap, it returns the maximum element.

Time Complexity: O(1)

3. Delete Root

To remove the root, replace it with the last element in the heap and then move that element downward until the heap property is restored. This process is called heapify-down or sift-down.

Time Complexity: O(log N)

4. Build Heap

A heap can be constructed from an unsorted array using bottom-up heapification. Starting from the last non-leaf node, repeatedly apply heapify-down to each node.

The bottom-up build-heap algorithm runs in O(N) time.

4. Array Representation of a Binary Heap

Because a binary heap is a complete binary tree, it can be stored efficiently in an array. No explicit left-child or right-child references are required.

Heap Tree:

        10
       /  \
      20   15
     / \   /
    30 40 25

Array:
[10, 20, 15, 30, 40, 25]

Parent of index i: (i - 1) / 2
Left child of index i: 2 × i + 1
Right child of index i: 2 × i + 2

5. Java PriorityQueue

Java provides the PriorityQueue class, which is implemented using a priority heap. By default, Java's PriorityQueue behaves as a Min Heap, meaning the smallest element has the highest priority.

              
            
Java
Use PriorityQueue as a Min Heap in Java
import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(30);
        pq.add(10);
        pq.add(20);
        pq.add(5);

        System.out.println("Smallest: " + pq.peek());

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

The peek() method returns the smallest element without removing it, while poll() removes and returns the smallest element.

6. Implementing a Max Heap in Java

Java's PriorityQueue can also behave as a Max Heap by supplying a reverse-order comparator.

              
            
Java
Use PriorityQueue as a Max Heap in Java
import java.util.PriorityQueue;
import java.util.Collections;

public class MaxHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq =
                new PriorityQueue<>(Collections.reverseOrder());

        pq.add(30);
        pq.add(10);
        pq.add(50);
        pq.add(20);

        System.out.println("Largest: " + pq.peek());

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

7. Time and Space Complexity

The main operations of a binary heap have the following complexity:

Operation          Time Complexity
Insert             O(log N)
Peek               O(1)
Delete Root        O(log N)
Build Heap         O(N)
Search             O(N)

A binary heap containing N elements requires O(N) space.

Unlike a Binary Search Tree, a heap does not provide efficient arbitrary-element searching. Its primary strength is maintaining fast access to the minimum or maximum element.

8. Heap Sort

Heap Sort uses a heap to sort an array efficiently. For ascending order, a Max Heap can be used to repeatedly move the largest element to the end of the array.

The overall time complexity of Heap Sort is O(N log N), and the standard in-place implementation requires O(1) additional array space apart from the input array.

Heap Sort provides predictable O(N log N) worst-case time complexity, although it is generally less cache-friendly than algorithms such as Quick Sort in many practical situations.

9. Heap vs Priority Queue

A heap is a data structure used to maintain an ordering relationship between elements. A Priority Queue is an abstract data type that provides access to the highest-priority element and is commonly implemented using a heap.

Heap: Defines the underlying structure and ordering rules.
Priority Queue: Defines operations such as insert, peek, and remove-highest-priority.
Min Heap Priority Queue: Removes the smallest element first.
Max Heap Priority Queue: Removes the largest element first.

10. Real-World and Algorithmic Applications

Priority Queues: Process tasks according to priority rather than insertion order.
Dijkstra's Algorithm: Efficiently select the next vertex with the smallest tentative distance.
Heap Sort: Sort elements in O(N log N) time.
Top-K Problems: Efficiently find the largest or smallest K elements.
Scheduling Systems: Select the next task based on priority, deadline, or other ranking criteria.
Event Simulation: Process events according to their scheduled time or priority.
Graph Algorithms: Support priority-based processing in several shortest-path and minimum-spanning-tree algorithms.

11. Common Mistakes

Confusing a Heap with a Binary Search Tree.
Assuming every element in a Min Heap is smaller than every element in its descendants.
Forgetting to restore the heap property after insertion or deletion.
Using incorrect parent and child index formulas.
Assuming that a heap provides O(log N) search for arbitrary elements.
Confusing the behavior of Min Heap and Max Heap.
Assuming Java PriorityQueue is a Max Heap by default. It is a Min Heap by default.

Conclusion

A Heap is an efficient complete binary tree-based data structure designed to provide fast access to the minimum or maximum element. Min Heaps keep the smallest element at the root, while Max Heaps keep the largest element at the root.

Insertion and root deletion take O(log N), while accessing the root takes O(1). Building a heap from an array can be done in O(N) time.

Heaps are especially useful for Priority Queues, Heap Sort, scheduling systems, Top-K problems, and graph algorithms such as Dijkstra's algorithm. Understanding heaps also provides a strong foundation for advanced algorithmic problem solving.