← Back to DSA Course | Chapter 12: Heaps | Lesson 3 of 5

Heap Sort Algorithm क्या है

Heap sort पहले top पर सबसे बड़े के साथ एक pyramid बनाता है और फिर top item को लेते रहता है और इसे आखिर में रखता है।

In this page:

  1. Heap Sort Idea
  2. Build Max Heap
  3. Move Maximum
  4. Complexity
  5. Practice
Syntax
markup 
def heapify(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

for i in range(n // 2 - 1, -1, -1):
    heapify(arr, n, i)
for end in range(n - 1, 0, -1):
    arr[0], arr[end] = arr[end], arr[0]
    heapify(arr, end, 0)

Heap Sort Idea

Heap sort दो phases में काम करता है: पहले यह input array को एक valid max heap में rearrange करता है, और फिर यह bार-बार heap के root से maximum value extract करता है और इसे array के आखिर में रखता है, हर बार heap को एक से छोटा करते हुए।

उदाहरण: Heap Sort Idea

#include <iostream>
using namespace std;
int main() {
    int arr[] = {4,10,3,5,1};
    cout << "Phase 1: build max heap. Phase 2: repeatedly extract max to the end" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Phase 1: build max heap. Phase 2: repeatedly extract max to the end");
    }
}
print("Phase 1: build max heap. Phase 2: repeatedly extract max to the end")
#include <stdio.h>
int main() {
    printf("Phase 1: build max heap. Phase 2: repeatedly extract max to the end\n");
    return 0;
}

Build Max Heap

Max heap बनाना आखिरी non-leaf node से शुरू होता है और root की ओर पीछे काम करता है, हर node को इसकी सही position में sift down करते हुए — यह bottom-up approach एक समय में एक element insert करने के बजाय linear time में पूरी heap property बनाता है।

उदाहरण: Build Max Heap

#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }
}
int main() {
    int arr[] = {4,10,3,5,1}, n = 5;
    for (int i = n/2 - 1; i >= 0; i--) heapify(arr, n, i);
    cout << "Max heap built, root=" << arr[0] << endl;
    return 0;
}
public class Main {
    static void heapify(int[] arr, int n, int i) {
        int largest = i, l = 2*i+1, r = 2*i+2;
        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;
        if (largest != i) { int t=arr[i]; arr[i]=arr[largest]; arr[largest]=t; heapify(arr, n, largest); }
    }
    public static void main(String[] args) {
        int[] arr = {4,10,3,5,1};
        for (int i = arr.length/2 - 1; i >= 0; i--) heapify(arr, arr.length, i);
        System.out.println("Max heap built, root=" + arr[0]);
    }
}
def heapify(arr, n, i):
    largest = i
    l, r = 2*i+1, 2*i+2
    if l < n and arr[l] > arr[largest]: largest = l
    if r < n and arr[r] > arr[largest]: largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

arr = [4, 10, 3, 5, 1]
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
    heapify(arr, n, i)
print("Max heap built, root=", arr[0])
#include <stdio.h>
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2, t;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { t=arr[i]; arr[i]=arr[largest]; arr[largest]=t; heapify(arr, n, largest); }
}
int main() {
    int arr[] = {4,10,3,5,1}, n = 5;
    for (int i = n/2 - 1; i >= 0; i--) heapify(arr, n, i);
    printf("Max heap built, root=%d\n", arr[0]);
    return 0;
}

Move Maximum

चूंकि एक max heap का root हमेशा current largest value रखता है, extraction root को अभी तक unsorted हिस्से के आखिरी element के साथ swap करता है, heap को एक छोटा करता है, और फिर दोहराने से पहले heap property restore करने के लिए नए root को sift down करता है।

उदाहरण: Move Maximum

#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }
}
int main() {
    int arr[] = {10,5,3,4,1}, n = 5;
    swap(arr[0], arr[n-1]);
    heapify(arr, n-1, 0);
    cout << "Max moved to end, arr[4]=" << arr[4] << " new root=" << arr[0] << endl;
    return 0;
}
public class Main {
    static void heapify(int[] arr, int n, int i) {
        int largest = i, l = 2*i+1, r = 2*i+2;
        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;
        if (largest != i) { int t=arr[i]; arr[i]=arr[largest]; arr[largest]=t; heapify(arr, n, largest); }
    }
    public static void main(String[] args) {
        int[] arr = {10,5,3,4,1};
        int n = arr.length;
        int t = arr[0]; arr[0] = arr[n-1]; arr[n-1] = t;
        heapify(arr, n-1, 0);
        System.out.println("Max moved to end, arr[4]=" + arr[4] + " new root=" + arr[0]);
    }
}
def heapify(arr, n, i):
    largest = i
    l, r = 2*i+1, 2*i+2
    if l < n and arr[l] > arr[largest]: largest = l
    if r < n and arr[r] > arr[largest]: largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

arr = [10, 5, 3, 4, 1]
n = len(arr)
arr[0], arr[n-1] = arr[n-1], arr[0]
heapify(arr, n - 1, 0)
print("Max moved to end, arr[4]=", arr[4], "new root=", arr[0])
#include <stdio.h>
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2, t;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { t=arr[i]; arr[i]=arr[largest]; arr[largest]=t; heapify(arr, n, largest); }
}
int main() {
    int arr[] = {10,5,3,4,1}, n = 5, t;
    t = arr[0]; arr[0] = arr[n-1]; arr[n-1] = t;
    heapify(arr, n-1, 0);
    printf("Max moved to end, arr[4]=%d new root=%d\n", arr[4], arr[0]);
    return 0;
}

Complexity

चूंकि heap construction और repeated extraction दोनों पूरी तरह original array के अंदर होते हैं — कोई अलग output array की ज़रूरत नहीं — heap sort इसके O(n log n) time के ऊपर input से आगे सिर्फ O(1) extra space उपयोग करके चलता है।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
    cout << "Heap sort: O(n log n) time, O(1) extra space -- sorts in place within the original array" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Heap sort: O(n log n) time, O(1) extra space -- sorts in place within the original array");
    }
}
print("Heap sort: O(n log n) time, O(1) extra space -- sorts in place within the original array")
#include <stdio.h>
int main() {
    printf("Heap sort: O(n log n) time, O(1) extra space -- sorts in place within the original array\n");
    return 0;
}

Practice

[4, 10, 3, 5, 1] जैसे एक छोटे array पर heap sort trace करें: initial max heap बनाएं, फिर देखें कैसे हर extraction current maximum को इसकी final sorted position में आखिर में move करता है जबकि heap front से सिकुड़ता है।

उदाहरण: Practice

#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }
}
void heapSort(int arr[], int n) {
    for (int i = n/2-1; i >= 0; i--) heapify(arr, n, i);
    for (int i = n-1; i > 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); }
}
int main() {
    int arr[] = {4,10,3,5,1};
    heapSort(arr, 5);
    for (int v : arr) cout << v << " ";
    return 0;
}
public class Main {
    static void heapify(int[] arr, int n, int i) {
        int largest = i, l = 2*i+1, r = 2*i+2;
        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;
        if (largest != i) { int t=arr[i]; arr[i]=arr[largest]; arr[largest]=t; heapify(arr, n, largest); }
    }
    public static void main(String[] args) {
        int[] arr = {4,10,3,5,1};
        int n = arr.length;
        for (int i = n/2-1; i >= 0; i--) heapify(arr, n, i);
        for (int i = n-1; i > 0; i--) { int t=arr[0]; arr[0]=arr[i]; arr[i]=t; heapify(arr, i, 0); }
        for (int v : arr) System.out.print(v + " ");
    }
}
def heapify(arr, n, i):
    largest = i
    l, r = 2*i+1, 2*i+2
    if l < n and arr[l] > arr[largest]: largest = l
    if r < n and arr[r] > arr[largest]: largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

arr = [4, 10, 3, 5, 1]
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
    heapify(arr, n, i)
for i in range(n - 1, 0, -1):
    arr[0], arr[i] = arr[i], arr[0]
    heapify(arr, i, 0)
print(arr)
#include <stdio.h>
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2, t;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { t=arr[i]; arr[i]=arr[largest]; arr[largest]=t; heapify(arr, n, largest); }
}
int main() {
    int arr[] = {4,10,3,5,1}, n = 5, t;
    for (int i = n/2-1; i >= 0; i--) heapify(arr, n, i);
    for (int i = n-1; i > 0; i--) { t=arr[0]; arr[0]=arr[i]; arr[i]=t; heapify(arr, i, 0); }
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}
Related Topics

Heap Sort क्या है · Min Heap और Max Heap · Heap परिचय · Topological Sort क्या है

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. पहले element से heap बनाना बजाय आखिरी non-leaf (n / 2 - 1) से पीछे जाने के।
  2. Root को आखिर में swap करने के बाद heap size को i तक सिकोड़ना भूल जाना, इसलिए sorted elements वापस खींचे जाते हैं।
  3. एक min heap उपयोग करना और जगह पर ascending order की उम्मीद करना, जब maximum को आखिर में move करने पर एक max heap ascending order देता है।
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Min Heap and Max Heap Next Lesson → K Largest Elements

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.