# Insertion in Heaps

steps:

- increase the heap size by 1.
- Insert the new element at the end of the Heap.
- heapify this newly inserted element following a bottom-up approach.

Suppose the Heap is a Max-Heap as:

The new element to be inserted is 15.

steps:

Step 1: Insert the new element at the end.

Step 2: Heapify the new element following bottom-up

approach.

-> 15 is greater than its parent 4, swap them.

-> 15 is again greater than its parent 12 , swap them.

Therefore, the final heap after insertion is

and this follows the max heap properties.

**implementation**(for max heap):

arr[] is an array

n is the size

i is the node to be heapified

key is the inserted element.

in c++:

**void maxheapify(int arr[], int n, int i)
{
// Find parent
int parent = (i - 1) / 2;
if (parent >= 0) {
// For Max-Heap
// If current node is greater than its parent
// Swap both of them and call heapify again
// for the parent
if (arr[i] > arr[parent]) {
swap(arr[i], arr[parent]);
// Recursively heapify the parent node
maxheapify(arr, n, parent);
}
}
}
// Function to insert a new node to the Heap
void insertNode(int arr[], int& n, int Key)
{
// Increase the size of Heap by 1
n = n + 1;
// Insert the element at end of Heap
arr[n - 1] = Key;
// Heapify the new node following a
// Bottom-up approach
maxheapify(arr, n, n - 1);
}**

java:

** private void maxheapify(int i)
{
int n=size+1 ;
// Find parent
int parent = (i - 1) / 2;
if (parent >= 0) {
// For Max-Heap
// If current node is greater than its parent
// Swap both of them and call heapify again
// for the parent
if (arr[i] > arr[parent]) {
int temp=arr[parent];
arr[parent]=arr[i];
arr[i]=temp;
// swap
// Recursively heapify the parent node
maxheapify(parent);
}
}
}
// Function to insert key to heap
// Inserts a new element to max heap
public void insert(int element)
{
arr[++size] = element;
if(size>0)
heapify(size);
}
**

similar procedure for the

**min heap.**