Saturday, May 9, 2020

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
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 in "Heap sort algorithm"
build max heap

After build max-heap Arr will be

After build max-heap  in heap sort algorithm
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 sort algorithm
Solve the steps in heap in algorithm
After following all these steps 

Sorted Array in "heap sort"
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

0 Comments:

Post a Comment