Hello Coders, 👨🏻‍💻

Introduction

A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at the root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.

A heap is a tree-based data structure that satisfies the below properties:

1. A heap is a complete tree

2. A heap is either a Min-Heap or a Max-Heap

Here. We'll Discuss about the Binary heap:

Types of Heap:

There are majorly 2 types of Heap:

1. Min Heap

2. Max Heap

Min-Heap

In a Min-Heap the key present at the root node must be minimum among the keys present at all of it's children. The same property must be recursively true for all sub-trees in that Binary Tree.

Max-Heap

In a Max-Heap the key present at the root node must be the greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

Operations on Heap:

• Insertion: The process of inserting an element in Heap

• Deletion: The process of removing an element from the Heap

• Peek: Looking at the root of the Heap

• Heapify: a process of creating a heap from an array.

Array Representation of a Heap

Heap is stored in an array format but for simplicity, we represent it in a tree-based data structure.

if we have an array arr of size N and arr[i] is the ith element in the array such a that

0 <= i < n

• arr[0] will represent the root of the heap

• (2*i+1) will return the left child of the Heap

• (2*i+2) will return the right child of the Heap

• ((i-1)/2) will return the root of the current node

Heap Implementation

Below is the Implementation of the heap in C++,

// Max-Heap data structure in C++

#include <iostream>
#include <vector>
using namespace std;

void swap(int *a, int *b)
{
  int temp = *b;
  *b = *a;
  *a = temp;
}
void heapify(vector<int> &hT, int i)
{
  int size = hT.size();
  int largest = i;
  int l = 2 * i + 1;
  int r = 2 * i + 2;
  if (l < size && hT[l] > hT[largest])
    largest = l;
  if (r < size && hT[r] > hT[largest])
    largest = r;

  if (largest != i)
  {
    swap(&hT[i], &hT[largest]);
    heapify(hT, largest);
  }
}
void insert(vector<int> &hT, int newNum)
{
  int size = hT.size();
  if (size == 0)
  {
    hT.push_back(newNum);
  }
  else
  {
    hT.push_back(newNum);
    for (int i = size / 2 - 1; i >= 0; i--)
    {
      heapify(hT, i);
    }
  }
}
void deleteNode(vector<int> &hT, int num)
{
  int size = hT.size();
  int i;
  for (i = 0; i < size; i++)
  {
    if (num == hT[i])
      break;
  }
  swap(&hT[i], &hT[size - 1]);

  hT.pop_back();
  for (int i = size / 2 - 1; i >= 0; i--)
  {
    heapify(hT, i);
  }
}
void printArray(vector<int> &hT)
{
  for (int i = 0; i < hT.size(); ++i)
    cout << hT[i] << " ";
  cout << "\n";
}

int main()
{
  vector<int> heapTree;

  insert(heapTree, 3);
  insert(heapTree, 4);
  insert(heapTree, 9);
  insert(heapTree, 5);
  insert(heapTree, 2);

  cout << "Max-Heap array: ";
  printArray(heapTree);

  deleteNode(heapTree, 4);

  cout << "After deleting an element: ";

  printArray(heapTree);
}

Thanks for reading.....