Data Structures for Coding Interviews in C++/

...

/

Max Heap (Implementation)

Max Heap (Implementation)

Let's implement a max Heap.

We'll cover the following...

Max-heap Implementation #

Let’s start with some function declarations for the heap class.

C++
#include <iostream>
using namespace std;
template < typename T >
  class MaxHeap {
    private:    
      void percolateUp(int i) {}
      void maxHeapify(int i) {}
    public:
      MaxHeap() {}
      int size() {}
      T getMax() {}
      void insert(const T & key) {}
      void removeMax() {}
      void buildHeap(T *arr, int size);
  };

Structure of our MaxHeap #

Declaring the private elements #

C++
#include <iostream>
#include <vector>
using namespace std;
template < typename T >
  class MaxHeap {
    private:    
      void percolateUp(int i) {}
      void maxHeapify(int i) {}
    public:
     vector < T > h;
      inline int parent(int i) {
        return (i - 1) / 2;
      }
      inline int lchild(int i) {
        return i * 2 + 1;
      }
      inline int rchild(int i) {
        return i * 2 + 2;
      }
      MaxHeap() {}
      int size() {}
      T getMax() {}
      void insert(const T & key) {}
      void removeMax() {}
      void buildHeap(T *arr, int size);
  };

Implementing the constructor and size() #

C++
#include <iostream>
#include <vector>
using namespace std;
template < typename T >
  class MaxHeap {
    private:    
      void percolateUp(int i) {}
      void maxHeapify(int i) {}
    public:
     vector < T > h;
      inline int parent(int i) {
        return (i - 1) / 2;
      }
      inline int lchild(int i) {
        return i * 2 + 1;
      }
      inline int rchild(int i) {
        return i * 2 + 2;
      }
      MaxHeap() {
        h.resize(0);
      }
      int size() {
        return h.size(); 
      }
      T getMax() {}
      void insert(const T & key) {}
      void removeMax() {}
      void buildHeap(T *arr, int size);
  };

Implementing the getMax() function

This function returns the maximum value from the heap, which is the root, i.e., the first value in the list. It does not modify the heap itself. If the heap is empty, this function returns -1. The time complexity of this function is in O(1)O(1) constant time, which is what makes heaps so special!

C++
#include <iostream>
#include <vector>
using namespace std;
template < typename T >
  class MaxHeap {
    private:    
      void percolateUp(int i) {}
      void maxHeapify(int i) {}
    public:
     vector < T > h;
      inline int parent(int i) {
        return (i - 1) / 2;
      }
      inline int lchild(int i) {
        return i * 2 + 1;
      }
      inline int rchild(int i) {
        return i * 2 + 2;
      }
      MaxHeap() {
        h.resize(0);
      }
      int size() {
        return h.size(); 
      }
      T getMax() {
        if (size() <= 0){
          return -1;
        }
        else
          return h[0];
      }     
      void insert(const T & key) {}
      void removeMax() {}
      void buildHeap(T *arr, int size);
  };

Implementing the removeMax() function

This function removes the maximum value from the heap. It first checks if the length of the heap is 1. If true, it deletes the value at index 0. Then, it checks if the length of the heap is greater than 1 if it is, it swaps the maximum value with the last leaf node, deletes it, and restores the max heap property on the rest of the tree by calling the maxHeapify() function on it. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed or swapped.

C++
#include <iostream>
#include <vector>
using namespace std;
template < typename T >
  class MaxHeap {
    private:    
      void percolateUp(int i) {}
      void maxHeapify(int i) {}
    public:
     vector < T > h;
      inline int parent(int i) {
        return (i - 1) / 2;
      }
      inline int lchild(int i) {
        return i * 2 + 1;
      }
      inline int rchild(int i) {
        return i * 2 + 2;
      }
      MaxHeap() {
        h.resize(0);
      }
      int size() {
        return h.size(); 
      }
      T getMax() {
        if (size() <= 0){
          return -1;
        }
        else
          return h[0];
      }     
      void insert(const T & key) {}
      void removeMax() {
        if(size() == 1){
          h.pop_back();
        }
        else if(size() > 1){
          // Built-in function in STL which swaps the value of two variables
          swap(h[0], h[size()-1]);
          // Deletes last element
          h.pop_back();
          // Restore heap property
          maxHeapify(0);
        }
        else
          return;
      }
      void buildHeap(T *arr, int size);
  };

Implementing the insert() function

This function appends the given value to the heap list and calls the percolateUp() function on it. This function will keep on swapping the values of nodes until the heap property is restored. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed or swapped.

C++
#include <iostream>
#include <vector>
using namespace std;
template < typename T >
  class MaxHeap {
    private:    
      void percolateUp(int i) {}
      void maxHeapify(int i) {}
    public:
     vector < T > h;
      inline int parent(int i) {
        return (i - 1) / 2;
      }
      inline int lchild(int i) {
        return i * 2 + 1;
      }
      inline int rchild(int i) {
        return i * 2 + 2;
      }
      MaxHeap() {
        h.resize(0);
      }
      int size() {
        return h.size(); 
      }
      T getMax() {
        if (size() <= 0){
          return -1;
        }
        else
          return h[0];
      }     
      void insert(const T & key) {
        // Push elements into vector from the back
        h.push_back(key);
        // Store index of last value of vector in  variable i
        int i = size()-1;  
        // Restore heap property
        percolateUp(i);
      }
      void removeMax() {
        if(size() == 1){
          h.pop_back();
        }
        else if(size() > 1){
          // Built-in function in STL which swaps the value of two variables
          swap(h[0], h[size()-1]);
          // Deletes last element
          h.pop_back();
          // Restore heap property
          maxHeapify(0);
        }
        else
          return;
      }
      void buildHeap(T *arr, int size);
  };

Implementing the percolateUp() function

This function restores the heap property by swapping the value at a parent node if it is less than the value at a child node. After swapping, the function is called recursively on each parent node until the root is reached. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed and/or swapped.

C++
#include <iostream>
#include <vector>
using namespace std;
template < typename T >
  class MaxHeap {
    private:    
      //percolateUp()t is meant to restore the 
      //heap property going up from a node to the root.
      void percolateUp(int i) {
        if(i <= 0)
         return;
        else if(h[parent(i)] < h[i]){
         swap(h[i], h[parent(i)]);
         percolateUp(parent(i));
         }
      }
      void maxHeapify(int i) {}
    public:
      vector < T > h;
      inline int parent(int i) {
        return (i - 1) / 2;
      }
      inline int lchild(int i) {
        return i * 2 + 1;
      }
      inline int rchild(int i) {
        return i * 2 + 2;
      }
      MaxHeap() {
        h.resize(0);
      }
      int size() {
        return h.size(); 
      }
      T getMax() {
        if (size() <= 0){
          return -1;
        }
        else
          return h[0];
      }     
      void insert(const T & key) {
        // Push elements into vector from the back
        h.push_back(key);
        // Store index of last value of vector in  variable i
        int i = size()-1;  
        // Restore heap property
        percolateUp(i);
      }
      void removeMax() {
        if(size() == 1){
          h.pop_back();
        }
        else if(size() > 1){
          // Built-in function in STL which swaps the value of two variables
          swap(h[0], h[size()-1]);
          // Deletes last element
          h.pop_back();
          // Restore heap property
          maxHeapify(0);
        }
        else
          return;
      }
      void buildHeap(T *arr, int size);
  };

Implementing the maxHeapify() function

The maxHeapify() function restores the heap property after a node is removed. It restores the heap property, starting from a given node down to the leaves. It swaps the values of the parent nodes with the values of their largest child nodes until the heap property is restored. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed or swapped.

C++
#include "MaxHeap.h"
int main() {
  MaxHeap<int> heap;
  heap.insert(2);
  heap.insert(8);
  heap.insert(15);
  heap.insert(5);
  heap.insert(1);
  heap.insert(20);
  
  
  cout << heap.getMax() << endl;
  heap.removeMax();
  cout << heap.getMax() << endl;
  heap.removeMax();
  cout << heap.getMax() << endl;
  heap.insert(1000);
  cout << heap.getMax() << endl;
  
  return 0;
}

Building a max-heap

Let’s build a max-heap now. Suppose we have nn elements in an array which represents our heap. For every node to be positioned in accordance with the max-heap property, we call the maxHeapify method at every index of that array, starting from the bottom of the heap (lines 83-88).

C++
#include <iostream>
#include <vector>
using namespace std;
template < typename T >
  class MaxHeap {
    private:    
      //percolateUp()t is meant to restore the 
      //heap property going up from a node to the root.
      void percolateUp(int i) {
        if(i <= 0)
         return;
        else if(h[parent(i)] < h[i]){
         swap(h[i], h[parent(i)]);
         percolateUp(parent(i));
         }
      }
      void maxHeapify(int i) {
        int lc = lchild(i);
        int rc = rchild(i);
        int imax = i;
    
        if(lc < size()  &&  h[lc] > h[imax])
          imax = lc;
        if(rc < size()  &&  h[rc] > h[imax])
          imax = rc;         
        if(i != imax){
          swap(h[i], h[imax]);
          maxHeapify(imax);
        }
      }
    public:
      vector < T > h;
      inline int parent(int i) {
        return (i - 1) / 2;
      }
      inline int lchild(int i) {
        return i * 2 + 1;
      }
      inline int rchild(int i) {
        return i * 2 + 2;
      }
      MaxHeap() {
        h.resize(0);
      }
      int size() {
        return h.size(); 
      }
      T getMax() {
        if (size() <= 0){
          return -1;
        }
        else
          return h[0];
      }     
      void insert(const T & key) {
        // Push elements into vector from the back
        h.push_back(key);
        // Store index of last value of vector in  variable i
        int i = size()-1;  
        // Restore heap property
        percolateUp(i);
      }
      void removeMax() {
        if(size() == 1){
          h.pop_back();
        }
        else if(size() > 1){
          swap(h[0], h[size()-1]);
          // Deletes last element
          h.pop_back();
          // Restore heap property
          maxHeapify(0);
        }
        else
          return;
      }
      void buildHeap(T arr[], int size){
       // Copy elements of array into vector h 
        copy(&arr[0], &arr[size], back_inserter(h));
        for (int i = (size - 1)/2; i >= 0; i--){
            maxHeapify(i);
        }
     }
      void printHeap(){
        for(int i = 0; i <= size()-1; i++){
          cout << h[i] << " ";
        }
        cout << endl;
      }
  };

Let’s derive a tight bound for the complexity of building a heap.

Notice that we start from the bottom of the heap, i.e., i = size-1 (line 85). If the height of the heap is hh ...