Heap Sort Algorithm In Hindi and its examples

This chapter will help you to learn about Heap Sort Algorithm In Hindi and its examples and also learn about Heap time complexity and understand the concept for heap sort.

Heap Sort Algorithm In Hindi and its examples

एक सरणी को छाँटने में Heaps का उपयोग किया जा सकता है। Max-Heap में, maximum element हमेशा जड़ में होगा। Heap Sort सरणी के Sort करने के लिए Heap की इस संपत्ति का उपयोग करता है।

एक सरणी पर विचार करें जिसे Heap सॉर्ट का उपयोग करके सॉर्ट किया जाना है।

• शुरू में तत्वों का एक अधिकतम ढेर का निर्माण।
• मूल तत्व, जो कि Arr [1] है, में Arr का अधिकतम तत्व होगा। उसके बाद, इस तत्व को Arr के Last element के साथ स्वैप करें और अंतिम तत्व को छोड़कर अधिकतम ढेर को ढेर करें जो पहले से ही अपनी सही स्थिति में है और फिर एक द्वारा ढेर की लंबाई कम करें।
• Step 2 को दोहराएं, जब तक कि सभी तत्व अपनी सही स्थिति में न हों।

void heap_sort(int Arr[ ])

    {
        int heap_size = N;

        build_maxheap(Arr);
        for(int i = N; i >= 2 ; i-- )
        {
            swap|(Arr[ 1 ], Arr[ i ]);
            heap_size = heap_size - 1;
            max_heapify(Arr, 1, heap_size);
        }
    }

Time Complexity Heap Sort

max-heap has complexity O(logN). Fresh max-heap has complexity O(N). max-heapify Run N-1 Times In Heap Function so complexity of heap_sort function is O(NlogN)

Example:- 

See Dig. 6 element are present so build max heap

build max heap

After build max-heap Arr will be

After build max-heap 

Step 1: 8 को 5 के साथ स्वैप किया जाता है।

Step 2: 8 को ढेर से काट दिया जाता है क्योंकि 8 अब सही स्थिति में है और।

Step 3: मैक्स-हीप बनाया गया है और 7 को 3 के साथ स्वैप किया गया है।

Step 4: 7 को ढेर से काट दिया जाता है।

Step 5: अधिकतम ढेर बनाया गया है और 5 को 1 के साथ स्वैप किया गया है।

Step 6: 5 को ढेर से काट दिया जाता है।

Step 7: अधिकतम ढेर बनाया गया है और 4 को 3 के साथ स्वैप किया गया है।

Step 8: 4 को ढेर से काट दिया जाता है।

Step 9: अधिकतम ढेर बनाया गया है और 3 को 1 के साथ स्वैप किया गया है।

Step 10: 3 काट दिया गया है।

Solve the steps in heap in algorithm

After following all these steps 

Sorted Array

Java Program For Heap sort Algorithm 

public class HeapSort

{

    public void sort(int arr[])

    {

        int n = arr.length;

  

        // Build heap (rearrange array)

        for (int i = n / 2 - 1; i >= 0; i--)

            heapify(arr, n, i);

  

        // One by one extract an element from heap

        for (int i=n-1; i>0; i--)

        {

            // Move current root to end

            int temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

  

            // call max heapify on the reduced heap

            heapify(arr, i, 0);

        }

    }

  

    // To heapify a subtree rooted with node i which is

    // an index in arr[]. n is size of heap

    void heapify(int arr[], int n, int i)

    {

        int largest = i; // Initialize largest as root

        int l = 2*i + 1; // left = 2*i + 1

        int r = 2*i + 2; // right = 2*i + 2

  

        // If left child is larger than root

        if (l < n && arr[l] > arr[largest])

            largest = l;

  

        // If right child is larger than largest so far

        if (r < n && arr[r] > arr[largest])

            largest = r;

  

        // If largest is not root

        if (largest != i)

        {

            int swap = arr[i];

            arr[i] = arr[largest];

            arr[largest] = swap;

  

            // Recursively heapify the affected sub-tree

            heapify(arr, n, largest);

        }

    }

  

    /* A utility function to print array of size n */

    static void printArray(int arr[])

    {

        int n = arr.length;

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

            System.out.print(arr[i]+" ");

        System.out.println();

    }

  

    // Driver program

    public static void main(String args[])

    {

        int arr[] = {12, 11, 13, 5, 6, 7};

        int n = arr.length;

  

        HeapSort ob = new HeapSort();

        ob.sort(arr);

  

        System.out.println("Sorted array is");

        printArray(arr);

    }

}

C++ Program For Heap sort Algorithm 

#include <iostream>

  

using namespace std;

  

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap

void heapify(int arr[], int n, int i)

{

    int largest = i; // Initialize largest as root

    int l = 2*i + 1; // left = 2*i + 1

    int r = 2*i + 2; // right = 2*i + 2

  

    // If left child is larger than root

    if (l < n && arr[l] > arr[largest])

        largest = l;

  

    // If right child is larger than largest so far

    if (r < n && arr[r] > arr[largest])

        largest = r;

  

    // If largest is not root

    if (largest != i)

    {

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

  

        // Recursively heapify the affected sub-tree

        heapify(arr, n, largest);

    }

}

  

// main function to do heap sort

void heapSort(int arr[], int n)

{

    // Build heap (rearrange array)

    for (int i = n / 2 - 1; i >= 0; i--)

        heapify(arr, n, i);

  

    // One by one extract an element from heap

    for (int i=n-1; i>0; i--)

    {

        // Move current root to end

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

  

        // call max heapify on the reduced heap

        heapify(arr, i, 0);

    }

}

  

/* A utility function to print array of size n */

void printArray(int arr[], int n)

{

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

        cout << arr[i] << " ";

    cout << "\n";

}

  

// Driver program

int main()

{

    int arr[] = {12, 11, 13, 5, 6, 7};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    heapSort(arr, n);

  

    cout << "Sorted array is \n";

    printArray(arr, n);

}

Python Program For Heap sort Algorithm 

# To heapify subtree rooted at index i.

# n is size of heap

def heapify(arr, n, i):

    largest = i # Initialize largest as root

    l = 2 * i + 1     # left = 2*i + 1

    r = 2 * i + 2     # right = 2*i + 2

  

    # See if left child of root exists and is

    # greater than root

    if l < n and arr[i] < arr[l]:

        largest = l

  

    # See if right child of root exists and is

    # greater than root

    if r < n and arr[largest] < arr[r]:

        largest = r

  

    # Change root, if needed

    if largest != i:

        arr[i],arr[largest] = arr[largest],arr[i] # swap

  

        # Heapify the root.

        heapify(arr, n, largest)

  

# The main function to sort an array of given size

def heapSort(arr):

    n = len(arr)

  

    # Build a maxheap.

    for i in range(n//2 - 1, -1, -1):

        heapify(arr, n, i)

  

    # One by one extract elements

    for i in range(n-1, 0, -1):

        arr[i], arr[0] = arr[0], arr[i] # swap

        heapify(arr, i, 0)

  

# Driver code to test above

arr = [ 12, 11, 13, 5, 6, 7]

heapSort(arr)

n = len(arr)

print ("Sorted array is")

for i in range(n):

    print ("%d" %arr[i]),

Sorting Algorithm : - 

Bubble Sort Algorithm And sorting program in different language

bucket sort Algorithm In Hindi And Its Examples 

Selection sort algorithm And Its Examples

Counting sort Algorithm in hindi and Its Example 

Heap Sort Algorithm In Hindi and its examples 

Insertion sort Algorithm And Its Examples

Merge Sort Algorithm In HIndi And Its Examples

Quick Sort Algorithm And Its Examples in hindi