Summary On Heap.

Question

A Heap is a partially sorted binary tree. Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If α has child node β then −

                        key(α) ≥ key(β)

Why use a heap?
A heap can be thought of as a priority queue, the most important node will always be at the top, and when removed, its replacement will be the most important. This can be useful when coding algorithms that require certain things to processed in a complete order, but when you don't want to perform a full sort or need to know anything about the rest of the nodes. For instance, a well-known algorithm for finding the shortest distance between nodes in a graph, Dijkstra's Algorithm, can be optimized by using a priority queue. Heaps can also be used to sort data. 

As the value of parent is greater than that of child, this property generates Max Heap. Based on this criteria, a heap can be of two types −

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap − Where the value of the root node is less than or equal to either of its children.

Max-Heap − Where the value of the root node is greater than or equal to either of its children.

Both trees are constructed using the same input and order of arrival.

Heap Construction Algorithm

Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Heap Deletion Algorithm

Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

 

Given below a C Program to Implement a Heap & provide Insertion & Deletion Operation:-

#include <stdio.h>

int array[100], n;

main()

{

    int choice, num;           

    n = 0; /*Represents number of nodes in the heap*/

    while(1)

    {

        printf("1.Insert the element \n");

        printf("2.Display all elements \n");

        printf("3.Quit \n");

        printf("Enter your choice : ");

        scanf("%d", &choice);

        switch(choice)

        {

        case 1:

            printf("Enter the element to be inserted to the list : ");

            scanf("%d", &num);

            insert(num, n);

            n = n + 1;

            break;

        case 2:

            display();

            break;

        case 3:

            exit(0);

        default:

            printf("Invalid choice \n");

    } /*End  of switch */

} /*End of while */

} /*End of main()*/

 

display()

{

    int i;

    if (n == 0)

    {

        printf("Heap is empty \n");

        return;

    }

    for (i = 0; i < n; i++)

        {

  printf("%d ", array[i]);

        printf("\n");       

        }

} /*End of display()*/

 

insert(int num, int location)

{

    int parentnode;

    while (location > 0)

    {

        parentnode =(location - 1)/2;

        if (num <= array[parentnode])

        {

            array[location] = num;

            return;

        }

        array[location] = array[parentnode];

        location = parentnode;

    } /*End of while*/

    array[0] = num; /*assign number to the root node */

} /*End of insert()*/

 

Please go through this video--