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

Max Heap (Implementation)

Explore the implementation of max heaps in C++, focusing on core operations like insertion, removal, and retrieving the maximum element. Understand heap maintenance through percolateUp and maxHeapify functions, with detailed time complexity analysis. This lesson enables you to build efficient priority-based data structures using max heaps.

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 ...