Heap

    

        Heap must be a complete(almost) binary tree.

Types of Heap:

    Max Heap -> For every node parent > child

    Min Heap -> For every node parent < child

Height -> 

                log(n) Always

Insertion(Max heap):

                Insertion is done by following steps:

1. Insert element in the last of array or the tree form
2. Compere and swap the the parent until reach to the parent greater than element or reach the root

Some examples of Insertion

1. Insert element 40 in given tree

Step 1: Insert 40 at last

Step 2: Swap until reach greater parent or root

swapped 5 and 40 as 5 < 40

swapped 20 and 40 as 20 < 40

This is the final tree as we reached the root

2.Insert element 35 in the above tree:

Step 1: Insert 35 at last

Step 2: Swap until reach greater parent or root

Here swapped 20 and 35 as 20 < 35

Swapped 30 and 35 as 30 < 35

No more swap required as parent 40 > 35, so this is the final tree.

Code:

    Array -> arr

    First empty position -> n

    int parent(int i)

    {

        return (i-1)/2;

    }

    

    void Insert(int data)

    {

        arr[n] = data;

        int i = n;

        while(i > 0 && arr[i] > arr[parent(i)]

        {

            swap(arr[i],arr[parent(i)]);

            i = parent(i);

        }

        n++;

    }

 

 

    Time Complexity: log(h)

    h = height of tree i.e. log(n)

        as this is a complete binary tree

Deletion(Max Heap):

        Delete element with maximum priority, for Max heap it will be maximum element

    Deletion is done by following steps

        1. Select the root element and replace it with last element and delete last element

        2. Choose the greatest child select it

        3. If the selected child is greater, swap element with child and jump to step 2 else jump to step 5.

        4. If element become leaf node then jump to step 5

        5. Exit the program

Some example on deletion:

        Delete 40 from given Max Heap

        Replace 40 by 5 and delete last node (value 5)

        Greatest child is 35 and is greater than 5, swap them and apply again on 5

        Greatest child is 15 and is greater than 5, swap them and apply again on 5

        As 5 become leaf, so stop

        This is final heap after deletion of element 40

 Code:

    Array -> arr

    Last element position -> n

int Delete()

{ 

   n--;

   int data = arr[0];

   swap(arr[0],arr[n]) 

   arr[0] = arr[n];

    int i;

    i = -1;

    int greatest = 0;

    while(greatest != i)

    {

        i = greatest;

        if(arr[lchild(i)] > arr[greatest])

            greatest = lchild(i);

        if(arr[rchild(i) > arr[greatest])

            greatest = rchild(i);

        swap(arr[greatest],arr[i]);

    }

 return data; 

}