Max Heap is one of the most important data structures that a C++ programmer should be aware of. It is a type of binary heap tree structure which has the highest node value at the top. It is commonly used in priority queues, and for sorting and searching algorithms. In this article, we will discuss in detail how the tree structure works, and the time and space complexity of insertion, access, search and deletion operations on a Max Heap. We will also discuss C++ code examples to help understand each concept better.
What is a Max Heap?
A Max Heap is a type of binary tree structure where the highest node value is at the top. It is a complete binary tree which means that all levels of the tree are filled, except for the last level, and all nodes are as far left as possible. The parent node of a max heap is always greater than or equal to its two children nodes. This property is called the heap property.
Max Heap Tree Structure
The max heap tree structure is implemented using an array. The root node is at the 0th index of the array, and the following two equations are used to calculate the left and right child nodes of the parent node at index i:
- Left child node: 2*i + 1
- Right child node: 2*i + 2
The following code shows a sample implementation of a Max Heap in C++.
int main()
{
// Array representation of Max Heap
// 10
// / \
// 5 3
// / \
// 2 4
int heap[] = {10, 5, 3, 2, 4};
//Calculate the size of the heap
int size = sizeof(heap)/sizeof(heap[0]);
//Print the Max Heap
for (int i = 0; i < size; i++)
cout << heap[i] << " ";
// Calculating the left and right child of the root node
int left = (2 * 0) + 1;
int right = (2 * 0) + 2;
cout << "\nLeft Child of root node : " << heap[left]
<< " Right Child of root node : " << heap[right];
return 0;
}
// Output:
// 10 5 3 2 4
// Left Child of root node : 5 Right Child of root node : 3
Time Complexity of Max Heap
When it comes to the time complexity of insertion, access, search and deletion on a Max Heap, the average case time complexity is O(log n) while the worst-case time complexity is O(n).
Insertion
Insertion into a Max Heap is quite simple. The new node is inserted at the end of the array. This is done to maintain the complete binary tree structure of the Max Heap. Then, the new node is compared to its parent node, and if it is greater than its parent node, then it is swapped with the parent node. This process is repeated until the new node is less than or equal to its parent node.
The following code is an example of insertion in a Max Heap in C++.
// Function to insert a new node into the Max Heap
void insert(int heap[], int x, int& size)
{
// Insert the element at the end
int i = size;
heap[i] = x;
// Check if it breaks the heap property and fix it
while (i != 0 && heap[(i - 1) / 2] < heap[i]) {
// Swap the elements
int temp = heap[(i - 1) / 2];
heap[(i - 1) / 2] = heap[i];
heap[i] = temp;
i = (i - 1) / 2;
}
// Increase the size
size++;
}
Search
Searching for a node in a Max Heap is an O(n) operation. This is because the max heap structure is implemented using an array, and the search operation must go through each element in the array to find the node.
The following code is an example of searching for a node in a Max Heap in C++.
// Function to search for a node in the Max Heap
int search(int heap[], int x, int size)
{
// Traverse the heap
for (int i = 0; i < size; i++) {
if (heap[i] == x)
return i;
}
return -1;
}
Access
Accessing an element in a Max Heap is an O(1) operation. This is because the max heap structure is implemented using an array, and the access operation can be done in constant time.
The following code is an example of accessing an element in a Max Heap in C++.
// Function to access an element in the Max Heap
int access(int heap[], int i)
{
// Return the element at index 'i'
return heap[i];
}
Deletion
Deletion in a Max Heap is a bit more complicated than insertion, since the complete binary tree structure must be maintained. The node to be deleted is first swapped with the last node in the array. Then, the swapped node is compared to its children nodes, and if it is smaller than any of its children nodes, it is swapped with the larger of the two children nodes. This process is repeated until the node is greater than or equal to its children nodes.
The following code is an example of deletion from a Max Heap in C++.
// Function to delete a node from the Max Heap
void deleteNode(int heap[], int i, int& size)
{
// Swap the node with the last element
int temp = heap[i];
heap[i] = heap[size - 1];
heap[size - 1] = temp;
// Decrease the size
size--;
// Compare the new node with its children and swap
// it with the largest of the two children
while (i < size && heap[i] < heap[2 * i + 1]
|| heap[i] < heap[2 * i + 2]) {
if (heap[2 * i + 1] > heap[2 * i + 2]) {
int temp = heap[i];
heap[i] = heap[2 * i + 1];
heap[2 * i + 1] = temp;
i = 2 * i + 1;
}
else {
int temp = heap[i];
heap[i] = heap[2 * i + 2];
heap[2 * i + 2] = temp;
i = 2 * i + 2;
}
}
}
Space Complexity of Max Heap
The space complexity of a Max Heap is O(n), where n is the number of nodes in the Max Heap. This is because the max heap structure is implemented using an array, and the array must store each node in the Max Heap.
Conclusion
In this article, we discussed in detail about the Max Heap data structure in C++. We discussed how the tree structure works, and the time and space complexity of insertion, access, search and deletion operations on a Max Heap. We also discussed C++ code examples to help understand each concept better.
Exercises
Implement a function to insert a new node into a Max Heap.
// Function to insert a new node into the Max Heap
void insert(int heap[], int x, int& size)
{
// Insert the element at the end
int i = size;
heap[i] = x;
// Check if it breaks the heap property and fix it
while (i != 0 && heap[(i - 1) / 2] < heap[i]) {
// Swap the elements
int temp = heap[(i - 1) / 2];
heap[(i - 1) / 2] = heap[i];
heap[i] = temp;
i = (i - 1) / 2;
}
// Increase the size
size++;
}
Implement a function to search for a node in a Max Heap.
// Function to search for a node in the Max Heap
int search(int heap[], int x, int size)
{
// Traverse the heap
for (int i = 0; i < size; i++) {
if (heap[i] == x)
return i;
}
return -1;
}
Implement a function to access an element in a Max Heap.
// Function to access an element in the Max Heap
int access(int heap[], int i)
{
// Return the element at index 'i'
return heap[i];
}
Implement a function to delete a node from a Max Heap.
// Function to delete a node from the Max Heap
void deleteNode(int heap[], int i, int& size)
{
// Swap the node with the last element
int temp = heap[i];
heap[i] = heap[size - 1];
heap[size - 1] = temp;
// Decrease the size
size--;
// Compare the new node with its children and swap
// it with the largest of the two children
while (i < size && heap[i] < heap[2 * i + 1]
|| heap[i] < heap[2 * i + 2]) {
if (heap[2 * i + 1] > heap[2 * i + 2]) {
int temp = heap[i];
heap[i] = heap[2 * i + 1];
heap[2 * i + 1] = temp;
i = 2 * i + 1;
}
else {
int temp = heap[i];
heap[i] = heap[2 * i + 2];
heap[2 * i + 2] = temp;
i = 2 * i + 2;
}
}
}
Given an array of integers, sort it using a Max Heap.
// Function to sort an array using Max Heap
void sort(int arr[], int n)
{
// Build a heap from the array
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Heap sort
for (int i = n - 1; i >= 0; i--) {
// Swap the root element with the last element
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Heapify the reduced heap
heapify(arr, i, 0);
}
}
// Function to heapify the array
void heapify(int arr[], int n, int i)
{
// Find the largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}