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
Create a method in the MaxHeap class called “size()” that returns the number of elements in the heap.
public int size() {
return size;
}
Create a method in the MaxHeap class called “isEmpty()” that returns true if the heap is empty, and false otherwise.
public boolean isEmpty() {
return size == 0;
}
Create a method in the MaxHeap class called “heapSort()” that sorts the elements in the heap in ascending order.
public void heapSort() {
int n = size;
for (int i = n - 1; i >= 0; i--) {
int max = extractMax();
heap[i] = max;
}
}
Create a method in the MaxHeap class called “search()” that takes an element as a parameter and returns the index of the element in the heap.
public int search(int element) {
for (int i = 0; i < size; i++) {
if (heap[i] == element) {
return i;
}
}
return -1;
}
Create a method in the MaxHeap class called “print()” that prints out the elements in the heap.
public void print() {
for (int i = 0; i < size; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}