Max Heap in Java

How is Max Heap Represented?

A max heap can be represented using different methods, but the most common and efficient way is through an array. Here’s how it works:

Array Representation: In a max heap, the binary tree is represented as an array where:

• The root element is at index 0.
• For any element at index i:
  • The left child is located at index 2*i + 1.
  • The right child is located at index 2*i + 2.
  • The parent is located at index (i - 1) / 2.

Example 

Consider a max heap represented by the following array: [50, 30, 40, 20, 10].

The binary tree representation would look like this:

 50
      /  \
     30   40
    /  \
   20  10

In this representation:

• 50 is the root at index 0.
   
• 30 and 40 are the children of 50 at indices 1 and 2.
   
• 20 and 10 are the children of 30 at indices 3 and 4.

Implementation of Max Heap in Java

To work with a max heap in Java, you need to understand how to implement it. Here’s a basic structure:

1. HeapNode Class: Represents a single node in the heap.
    
2. MaxHeap Class: Manages the heap operations like insertion and deletion.

HeapNode Class

class HeapNode {
    int value;


    // Constructor
    HeapNode(int value) {
        this.value = value;
    }
}

MaxHeap Class

Here’s a simple implementation of a max heap in Java:

import java.util.ArrayList;
import java.util.Collections;
public class MaxHeap {
    private ArrayList<HeapNode> heap;
    // Constructor
    public MaxHeap() {
        heap = new ArrayList<>();
    }

    // Method to insert a value into the heap
    public void insert(int value) {
        HeapNode newNode = new HeapNode(value);
        heap.add(newNode);
        heapifyUp(heap.size() - 1);
    }

    // Method to remove and return the maximum value (root)
    public int extractMax() {
        if (heap.isEmpty()) {
            throw new IllegalStateException("Heap is empty");
        }
        int max = heap.get(0).value;
        HeapNode lastNode = heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) {
            heap.set(0, lastNode);
            heapifyDown(0);
        }
        return max;
    }


    // Helper method to maintain heap property after insertion
    private void heapifyUp(int index) {
        int parentIndex = (index - 1) / 2;
        if (index > 0 && heap.get(index).value > heap.get(parentIndex).value) {
            Collections.swap(heap, index, parentIndex);
            heapifyUp(parentIndex);
        }
    }


    // Helper method to maintain heap property after extraction
    private void heapifyDown(int index) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int largest = index;


        if (leftChild < heap.size() && heap.get(leftChild).value > heap.get(largest).value) {
            largest = leftChild;
        }
        if (rightChild < heap.size() && heap.get(rightChild).value > heap.get(largest).value) {
            largest = rightChild;
        }
        if (largest != index) {
            Collections.swap(heap, index, largest);
            heapifyDown(largest);
        }
    }


    // Method to print the heap
    public void printHeap() {
        for (HeapNode node : heap) {
            System.out.print(node.value + " ");
        }
        System.out.println();
    }
}

Key Features of Max Heap

• Max Element at Root: The maximum value is always at the root node.
   
• Efficient Insertion and Deletion: Insertion and extraction operations are efficient due to the heap structure.
   
• Heapify Operations: Maintaining heap properties involves heapify operations, which adjust the position of elements.

Example

Here’s how you can use the MaxHeap class:

• Java

Java

public class Main {
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap();

        maxHeap.insert(10);
        maxHeap.insert(20);
        maxHeap.insert(5);
        maxHeap.insert(30);

        System.out.println("Heap after insertions:");
        maxHeap.printHeap();  // Output: 30 20 5 10

        System.out.println("Extracted max value: " + maxHeap.extractMax()); // Output: 30

        System.out.println("Heap after extraction:");
        maxHeap.printHeap();  // Output: 20 10 5
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Heap after insertions:
30 20 5 10
Extracted max value: 30
Heap after extraction:
20 10 5

Explanation:

• After inserting values, the heap maintains the max heap property.
   
• Extracting the maximum value (30) from the heap adjusts the heap to maintain its properties.

Frequently Asked Questions

What is the time complexity of heap operations?

• Insertion: O(log n)
• Extraction (Removing Max): O(log n)
• Heapify Operations: O(log n)

How does a max heap differ from a min heap?

A max heap always has the largest element at the root, while a min heap has the smallest element at the root.

Can a max heap be used to implement a priority queue?

Yes, a max heap is commonly used to implement a priority queue where the highest-priority element is always accessible and can be extracted efficiently.

How does a max heap improve sorting performance?

In heap sort, a max heap allows efficient sorting by repeatedly extracting the maximum element and placing it in the correct position. This process sorts the elements in O(n log n) time.

Conclusion

Max heaps in java are powerful data structures that help in managing and organizing data efficiently. They ensure that the largest element is always accessible in constant time. By understanding how to implement and use max heaps in Java, you can leverage their efficiency for various applications, from sorting algorithms to real-time scheduling.

You can also practice coding questions commonly asked in interviews on Code360.