Max Heap in C++

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

// 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++; 
} 

// 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; 
} 

// Function to access an element in the Max Heap 
int access(int heap[], int i) 
{ 
    // Return the element at index 'i' 
    return heap[i]; 
} 

// 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; 
        } 
    } 
} 

// 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); 
    } 
}