Heap is a complete binary tree and is a type of Data Structure.
Heap satisfies a heap order property.
A binary tree, is a complete binary tree where in all the level are completely filled except the last level.
When adding the nodes, all the nodes will be added from left.
There are 2 different type of heaps:
1. Max Heap
2. Min Heap
1. Max Heap
A heap is a max heap if the child node values are less than that of its parent.
Meaning the greatest element will always be the root.
2. Min Heap
A heap is a min heap if the child node values are greater than that of its parent.
What are the other different type of heap data structure?
1. Binomial Heap:
2. Fibonacci Heap:
3. Leftist Heap:
4. Pairing Heap:
5. Skew Heap:
Max Heap Representation:
Even-though Max heap is a binary tree format, we will usually represent MaxHeap as an array.
As max heap is a complete binary tree, it will allow us to efficiently map the parent with its children.
For a node i,
Parent can be calculated as (i – 1) // 2
Left child can be calculated 2 * i + 1
Right child can be calculated 2 * i + 2
First non leaf node can be found at (n/2-1)
Basic Heap Operations:
Max Heap has below 3 operations;
Insertion
Deletion
Peek
Heapify: It is a property through which the heap property will be maintained.
There are 2 different types of heapify.
1. Heapify Up: Move the element up, if the element is larger than its parents.
2. Heapify Down: Move the element down, if it is smaller than its parent.
Max Heap Heapify operation
Heapify is an process through which a binary tree will be converted into heap data structure.
Consider the array below
Consider the complete binary tree as below:
We know that, the first non leaf node will be (n/2 -1)
So node with value 7 will be the first non leaf node.
Now set the current element as largest element.
Then calculate the left and right children of the element and check which of the child is largest.
Swap the largest element with the current element.
Now again go to the non leaf node and repeat the above steps until all the sub trees are heapified.
Max Heap Insertion;
To insert a node in a heap,
Check if there are no nodes, then the current node will be the root.
If there are some nodes, then insert the current node at the end of the tree from left to right.
Then heapify the tree.
Max Heap Deletion;
To delete the node, swap the node to be deleted to the last leaf node.
Then delete the leaf node.
Then heapify the whole tree
Max Heap Peek;
Peek function will return max or min element.
To do that, just return the root node.
Code
#include <iostream>
#include <vector>
using namespace std;
void heapify(vector<int> &arr, int i)
{
int size = arr.size();
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && arr[l] > arr[largest])
largest = l;
if (r < size && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
swap(arr[i], arr[largest]);
heapify(arr, largest);
}
}
void insert(vector<int> &arr, int val)
{
arr.push_back(val);
int current = arr.size() - 1;
while (current > 0)
{
int parent = (current - 1) / 2;
if (arr[current] > arr[parent])
{
swap(arr[current], arr[parent]);
current = parent;
}
else
{
break;
}
}
}
void deleteNode(vector<int> &arr, int num)
{
int size = arr.size();
int i;
for (i = 0; i < size; i++)
{
if (num == arr[i])
break;
}
swap(arr[i], arr[size - 1]);
arr.pop_back();
size = arr.size();
if (i < size)
{
heapify(arr, i);
}
}
void printArray(const vector<int> &arr)
{
for (int num : arr)
cout << num << " ";
cout << "\n";
}
int main()
{
vector<int> arr;
insert(arr, 8);
insert(arr, 14);
insert(arr, 7);
insert(arr, 4);
insert(arr, 9);
insert(arr, 10);
cout << "Max Heap: ";
printArray(arr);
deleteNode(arr, 14);
cout << "After delete: ";
printArray(arr);
return 0;
}
Output:
Max Heap: 14 9 10 4 8 7
After delete: 10 9 7 4 8