introduction to heaps
A heap is a specialized treebased data structure and satisfies the below properties:
 A Heap is a complete tree. what is a complete tree? in a complete tree all levels are completely filled except possibly the last level and the last level has all keys as left as possible.
 A Heap is either Min Heap or Max Heap. In a MinHeap, the key at root must be minimum among all keys present in the Binary Heap. The same property must be recursively true for all nodes in the Tree. In a MaxHeap, the key at root must be maximum among all keys present in the Binary Heap. The same property must be recursively true for all nodes in the Tree
Binary Heap: A Binary Heap is a heap where each node can have at most two children. a Binary Heap is nothing but a Binary Tree satisfying the above heap properties.
max heap:
min heap:
Binary Heaps representation:
they are represented using arrays: The root element will be at Arr[0].

for ith node, Arr[i]:
Arr[(i1)/2] will be parent node Arr[(2*i)+1] will be the left child node Arr[(2*i)+2] will be the right child node
Finding Maximum Element: In a MaxHeap, the maximum element is always present at the root node and that is first element in the array which is used to represent the Heap. so maximum element Arr[0] can be obtained in O(1) time complexity.
Finding Minimum Element: In a MinHeap, the minimum element is always present at the root node and that is first element in the array which is used to represent the Heap. so minimum element Arr[0] can be obtained in O(1) time complexity.
Heapifying :
when we insert an element in heap, it doesnt follow the property of heap. so we place the element at the correct position to satisfy the Heap property this process is Heapify.Heapifying in a Max Heap: In Max Heap every node's value must be greater than the values of its children nodes. So, to heapify a particular node swap the value of the node with the maximum value of its children nodes and continue the process until all of the nodes below it satisfies the Heap property.
consider the below heap as a MaxHeap:
In the above heap, node 5 does not follow the Heap property. Let's
heapify the root node, node 5.
Step 1: Swap the node 5 with the maximum of its childrens i.e.,
max(12, 4).
Step 2: Again the node 5 does not follow the heap property. Swap the
node 5 with the maximum of its new childrens i.e., max(7, 2).
The Node 5 is now heapified successfully and placed at it's correct
position.
Time Complexity: The time complexity to heapify a single node is O(h), where h is equal to log(N) in a complete binary tree where N is the total number of nodes.
Time Complexity: The time complexity to heapify a single node is O(h), where h is equal to log(N) in a complete binary tree where N is the total number of nodes.
implementation (for max heap):
arr[] is an array
n is the size
i is the node to be heapified
in c++:
void maxheapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected subtree
maxheapify(arr, n, largest);
}
}
in java:
static void maxheapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected subtree
maxheapify(arr, n, largest);
}
}
similarly Heapifying can be done in a min Heap
implementation (for min heap):
in c++:
void minheapify(int arr[], int n, int i)
{
int smallest = i; // Initialize smallest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is smaller than root
if (l < n && arr[l] < arr[smallest])
smallest = l;
// If right child is smaller than smallest so far
if (r < n && arr[r] < arr[smallest])
smallest = r;
// If smallest is not root
if (smallest != i) {
swap(arr[i], arr[smallest]);
// Recursively heapify the affected subtree
minheapify(arr, n, smallest);
}
}
in java:
static void minheapify(int arr[], int n, int i)
{
int smallest = i; // Initialize smallest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is smaller than root
if (l < n && arr[l] < arr[smallest])
smallest = l;
// If right child is smaller than smallest so far
if (r < n && arr[r] < arr[smallest])
smallest= r;
// If smallest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[smallest];
arr[smallest] = swap;
// Recursively heapify the affected subtree
minheapify(arr, n, smallest);
}
}