Heap Data Structure using C Programming - BunksAllowed

BunksAllowed

BunksAllowed is an effort to facilitate Self Learning process through the provision of quality tutorials.

Community

Join WhatsApp Grpup using https://chat.whatsapp.com/EAcqRurEOXb52Ax7Tlmj9I

  • Home
    • demo-image
    Home Data Structures Technology Heap Data Structure using C Programming

    Heap Data Structure using C Programming

    Share This

    Heaps are one type of data structure where elements are stored in two fashions either every parent element is greater than their children or is smaller than their children. Below we will discuss the two fashions.

    Max-Heap

    A max heap is a complete binary tree such that for each node, the key value in the node is greater than or equal to the value in its children. Observe that this implies that the root contains the largest value in the tree.

    max-heap

    Min-Heap

    A min-heap is a complete binary tree such that for each node, the key value in the node is smaller than or equal to the value in its children. Observe that this implies that the root contains the smallest value in the tree which is shown in the following Figure.

    min_heap

    In either case of the above said two types of the heap the binary tree will grow in that way: parent(2*i),left-child(2*i+1), and right-child(2*i+2), where i ∈ [0,n]. When we insert or delete an element every time we have to maintain the heap property. Below we will give an example to clarify the insertion and deletion where the MAX-HEAP property is maintained which is clearly shown in the following figures. Suppose we have a complete binary tree which is shown below.

    max_heap_array
    heap_insert4
    heap_insert2

    When we delete always the root element will be deleted and after that we have to maintain the heap property so that the rest of the elements are properly placed. Below we will see a clear picture of deletion.

    heap_delete
    Source Code of Max-Heap
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #define MAX 50
    void insert(int *,int,int,int);
    void down_adjust(int *,int);
    void display(int *,int);
    void del_hi_priori(int *,int,int);
    void swap(int *,int *);
    int main()
    {
    int *heap,n,i,lb,last,temp,choice,data;
    heap=(int *)malloc(sizeof(int)*MAX);
    n=0;
    lb=0;
    while(1)
    {
    printf("\n.....MAIN MENU.....");
    printf("\n1.Insert");
    printf("\n2.Delete");
    printf("\n3.Display");
    printf("\n4.Quit");
    printf("\nEnter your choice : ");
    scanf("%d",&choice);
    switch(choice)
    {
    case 1:printf("\nEnter data to be inserted : ");
    scanf("%d",&data);
    insert(heap,n,data,lb);
    n++;
    break;
    case 2:del_hi_priori(heap,n,0);
    n--;
    break;
    case 3:display(heap,n);
    break;
    case 4:return 0;
    }
    }
    return 0;
    }
    void insert(int *heap,int heapsize,int data,int lb)
    {
    int i,p;
    int parent(int);
    if(heapsize==MAX)
    {
    printf("Queue Is Full!!");
    }
    i=lb+heapsize;
    heap[i]=data;
    while(i>lb && heap[p=parent(i)]<heap[i])
    {
    swap(&heap[p],&heap[i]);
    i=p;
    }
    }
    void del_hi_priori(int *heap,int heapsize,int lb)
    {
    int i,t,p;
    if(heapsize==0)
    {
    printf("Queue Is Empty!!");
    }
    t=heap[0];
    printf("\nElement %d is deleted",t);
    swap(&heap[0],&heap[heapsize-1]);
    i=1;
    while(i>lb && heap[p=parent(i)]<heap[i])
    {
    swap(&heap[p],&heap[i]);
    i=p;
    }
    }
    int parent(int i)
    {
    float p;
    p=((float)i/2.0)-1.0;
    return ceil(p);
    }
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

    Happy Exploring!

    Tags
    Share This
    bunksAllowed

    About BunksAllowed

    Newer Article Graph Traversal using Breadth First Search (BFS) Older Article Double Ended Queue (Deque) using C Programming
    By on
    Labels: ,
    Subscribe to: Post Comments (Atom)
    Comment Using!!

    No comments:

    Post a Comment

    Note: Only a member of this blog may post a comment.

    About BunksAllowed