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.

Press + to interact
main.cpp
MaxHeap.h
#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 #

Press + to interact
main.cpp
MaxHeap.h
#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() #

Press + to interact
main.cpp
MaxHeap.h
#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) ...

Access this course and 1400+ top-rated courses and projects.