AI Features
Home
Courses
Data Structures for Coding Interviews in C++

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++
Files
#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++
Files
#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++
Files
#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++
Files
#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() ...