A heap is a complete binary tree in which every node key is compared with its children and arranged accordingly. It is also called as a binary heap.
It has two properties :
The ordering is of two types:
Min heap : A min heap is a complete binary tree in which the key value in each node is smaller than or equal to the key values in its child node.
As heap is a complete binary tree, height of the tree will be logN
Heaps can be easily represented as an array since it is a complete binary tree.
Array-based representation is space-efficient.
The process of creating a heap data structure froma binary tree is known as Heapify.
Min-Heap or a Max-Heap are constructed using this process.
2i + 1
2i + 2
.void Heapify(vector<int> &heap, int i)
{
int size = heap.size();
int largest = i;
int l = 2 * i + 1; //left child
int r = 2 * i + 2; //right child
if (l < size && heap[l] > heap[largest])
largest = l;
if (r < size && heap[r] > heap[largest])
largest = r;
if (largest != i)
{
swap(&heap[i], &heap[largest]); // perform swapping
Heapify(heap, largest);
}
}
Inserting in a Max heap
Note :For
Min Heap
, parent node is always smaller than newNode.
void insert(vector<int> &heap, int val)
{
int size = heap.size();
if (size == 0)
{
heap.push_back(val);
}
else
{
heap.push_back(val);
for (int i = size/2-1; i >= 0; i--)
{
heapify(heap, i);
}
}
}
To delete a node in Max heap
:
Note : For
Min Heap
, both child nodes are greater than the current node.
void hDelete(vector<int> &heap, int val)
{
int size = heap.size();
int i;
for (i = 0; i < size; i++)
{
if (val == heap[i])
break;
}
swap(&heap[i], &heap[size - 1]);
heap.pop_back();
for (int i = size/2-1; i >= 0; i--)
{
heapify(heap, i);
}
}