Heap Sort (हीप सॉर्ट )

Heap Sort (हीप सॉर्ट ):-

Heap sort is a comparison based sorting method based on Binary Heap data structure. It is similar to selection sort, In which we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining elements.

A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap. The heap can be represented by binary tree or array.

If the parent node is stored at index K, the left child can be calculated by 2 * K + 1 and right child by 2 * K + 2 .

Complexity of Heap Sort in Best case, Avg case and Worst case is O(nlogn).

हीप सॉर्ट तुलना पर आधारित सॉर्टिंग मेथड है जो बाइनरी हीप डाटा स्ट्रक्चर का प्रयोग करती है। यह सिलेक्शन सॉर्ट के सामान ही होती है जिसमे हम सर्वप्रथम सबसे बड़े एलिमेंट को खोजकर उसे डाटा स्ट्रक्चर के अंत में रखते है। इसके पश्चात् यही कार्य पुनः शेष एलेमेंट्स के लिए किया जाता है।

एक बाइनरी हीप एक कम्पलीट बाइनरी ट्री होता है जिसमे आइटम को एक विशेष क्रम में इस प्रकार रखा जाता है कि पैरेंट नोड की वैल्यू उसके दोनों चाइल्ड नोड की वैल्यू से बढ़ी (या छोटी) होती है इसे क्रमश 'मैक्स हीप' या 'मीन हीप' कहा जाता है। हीप को बाइनरी ट्री या ऐरे द्वारा प्रदर्शित किया जा सकता है।

यदि पैरेंट नोड को इंडेक्स K पर रखा गया है तब इसके लेफ्ट चाइल्ड को 2*K+1 एवं राईट चाइल्ड को 2*K+2 पर रखा जायेगा। 

बेस्ट , एवरेज एवं वर्स्ट केस में हीप सॉर्ट की कॉम्प्लेक्सिटी O(nlogn) होती है। 

Heap Sort Algorithm:-

1. Build a max heap from the input data.

2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify(MaxHeap) the root of tree.

3. Repeat above steps while size of heap is greater than 1.

C Program to sort elements of an array based on heap sort algorithm (MAX heap):-

#include <stdio.h>

#include<conio.h>

void main()

{

    

int heap[10], no, i, j, c, root, temp;

clrscr();

printf("\n Enter the number of elements:");

scanf("%d", &no);

printf("\n Enter the values of nodes: ");

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

scanf("%d",&heap[i]);

for (i = 1; i < no; i++)

    {

        c = i;

        do

        {

            root = (c - 1) / 2;             

            if (heap[root] < heap[c])   /* to create MAX heap array */

            {

                temp = heap[root];

                heap[root] = heap[c];

                heap[c] = temp;

            }

            c = root;

        } while (c != 0);

    }

 

    printf("Heap array : ");

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

        printf("%d\t ", heap[i]);

    for (j = no - 1; j >= 0; j--)

    {

        temp = heap[0];

        heap[0] = heap[j];   /* swap max element with rightmost leaf element */

        heap[j] = temp;

        root = 0;

        do 

        {

            c = 2 * root + 1;    /* left node of root element */

            if ((heap[c] < heap[c + 1]) && c < j-1)

                c++;

            if (heap[root]<heap[c] && c<j)    /* again rearrange to max heap array */

            {

                temp = heap[root];

                heap[root] = heap[c];

                heap[c] = temp;

            }

            root = c;

        } while (c < j);

    } 

    printf("\n The sorted array is : ");

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

    printf("\t %d", heap[i]);

   }