Max Heap in Java

Max heap is a type of binary heap data structure that is used to store data in a specific order. A max heap is a complete binary tree that has the property that for any given node, the value of the node is greater than or equal to the value of its children. This property is called the “max heap property”. Max heaps are used to store data efficiently and are used in many applications such as priority queues, sorting algorithms, and graph algorithms. In this article, we will discuss how max heaps work, the time and space complexities associated with different operations, and some example Java code to help you understand.

What is a Max Heap?

A max heap is a complete binary tree that has the property that for any given node, the value of the node is greater than or equal to the value of its children. This property is called the “max heap property”. Max heaps are used to store data efficiently and are used in many applications such as priority queues, sorting algorithms, and graph algorithms.

A max heap is a complete binary tree which means that all levels are filled except for the last level which may not be filled completely. This means that the number of nodes in a max heap is always a power of 2 minus 1 (2n – 1).

Max heaps are typically represented as an array. Each node of the max heap is stored in consecutive positions of the array. The root node is always stored in the first position of the array (index 0) and the last node is always stored in the last position of the array (index n-1).

Time Complexity

The time complexity of a max heap depends on the operation being performed. The average time complexity for the following operations is given below.

• Access: O(1)
• Search: O(n)
• Insertion: O(log n)
• Deletion: O(log n)

Space Complexity

The space complexity of a max heap is O(n). This means that the max heap requires O(n) memory to store n elements.

Example Java Code for Max Heap

Let’s take a look at some example Java code for max heap. First, we will create a class called MaxHeap that will handle all of the operations for a max heap.

public class MaxHeap { 
    int[] heap; 
    int capacity; 
    int size; 
 
    public MaxHeap(int capacity) { 
        this.capacity = capacity; 
        heap = new int[capacity]; 
    } 
 
    public int getLeftChildIndex(int parentIndex) { 
        return 2 * parentIndex + 1; 
    } 
 
    public int getRightChildIndex(int parentIndex) { 
        return 2 * parentIndex + 2; 
    } 
 
    public int getParentIndex(int childIndex) { 
        return (childIndex - 1) / 2; 
    } 
 
    public boolean hasLeftChild(int index) { 
        return getLeftChildIndex(index) < size; 
    } 
 
    public boolean hasRightChild(int index) { 
        return getRightChildIndex(index) < size; 
    } 
 
    public boolean hasParent(int index) { 
        return getParentIndex(index) >= 0; 
    } 
 
    public int leftChild(int index) { 
        return heap[getLeftChildIndex(index)]; 
    } 
 
    public int rightChild(int index) { 
        return heap[getRightChildIndex(index)]; 
    } 
 
    public int parent(int index) { 
        return heap[getParentIndex(index)]; 
    } 
 
    public void swap(int index1, int index2) { 
        int temp = heap[index1]; 
        heap[index1] = heap[index2]; 
        heap[index2] = temp; 
    } 
 
    public void insert(int element) { 
        ensureExtraCapacity(); 
        heap[size] = element; 
        size++; 
        heapifyUp(); 
    } 
 
    public int max() { 
        if (size == 0) { 
            throw new IllegalStateException(); 
        } 
        return heap[0]; 
    } 
 
    public int extractMax() { 
        if (size == 0) { 
            throw new IllegalStateException(); 
        } 
        int max = heap[0]; 
        heap[0] = heap[size - 1]; 
        size--; 
        heapifyDown(); 
        return max; 
    } 
 
    public void delete(int index) { 
        heap[index] = Integer.MAX_VALUE; 
        heapifyUp(); 
        extractMax(); 
    } 
 
    public void heapifyUp() { 
        int index = size - 1; 
        while (hasParent(index) && parent(index) < heap[index]) { 
            swap(getParentIndex(index), index); 
            index = getParentIndex(index); 
        } 
    } 
 
    public void heapifyDown() { 
        int index = 0; 
        while (hasLeftChild(index)) { 
            int smallerChildIndex = getLeftChildIndex(index); 
            if (hasRightChild(index) && rightChild(index) > leftChild(index)) { 
                smallerChildIndex = getRightChildIndex(index); 
            } 
            if (heap[index] > heap[smallerChildIndex]) { 
                break; 
            } else { 
                swap(index, smallerChildIndex); 
            } 
            index = smallerChildIndex; 
        } 
    } 
 
    public void ensureExtraCapacity() { 
        if (size == capacity) { 
            heap = Arrays.copyOf(heap, capacity * 2); 
            capacity *= 2; 
        } 
    } 
} 

Conclusion

Max heaps are a type of binary heap data structure that is used to store data in a specific order. Max heaps are a complete binary tree that has the property that for any given node, the value of the node is greater than or equal to the value of its children. Max heaps are typically represented as an array and are used in many applications such as priority queues, sorting algorithms, and graph algorithms. The time complexity of a max heap depends on the operation being performed, with access having an average time complexity of O(1), search having an average time complexity of O(n), insertion having an average time complexity of O(log n), and deletion having an average time complexity of O(log n). The space complexity of a max heap is O(n).

Exercises

public int size() { 
    return size; 
}

public boolean isEmpty() { 
    return size == 0; 
} 

public void heapSort() { 
    int n = size; 
    for (int i = n - 1; i >= 0; i--) { 
        int max = extractMax(); 
        heap[i] = max; 
    } 
} 

public int search(int element) { 
    for (int i = 0; i < size; i++) { 
        if (heap[i] == element) { 
            return i; 
        } 
    } 
    return -1; 
} 

public void print() { 
    for (int i = 0; i < size; i++) { 
        System.out.print(heap[i] + " "); 
    } 
    System.out.println(); 
}