← Back to DSA Course | Chapter 9: Sorting Algorithms | Lesson 6 of 9

Heap Sort क्या है

Heap sort एक tournament जैसा है जहां सबसे बड़ा number हमेशा एक tree के top तक उठता है, हटाया जाता है और आखिर में रखा जाता है, और tree फिर से बनाया जाता है।

In this page:

  1. Basic Idea
  2. Step by Step
  3. Small Array
  4. Practice
  5. Summary
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)

Basic Idea

Heap sort पहले array को एक max heap में rearrange करता है, जहां हर parent value इसके children से कम से कम उतनी बड़ी है, फिर top से सबसे बड़ी value बार-बार हटाता है और इसे array के आखिर में रखता है जब तक कुछ न बचे।

उदाहरण: Basic Idea

#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 x : arr) cout << x << " ";
	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); }
	}
	static 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--) { int t = arr[0]; arr[0] = arr[i]; arr[i] = t; heapify(arr, i, 0); }
	}
	public static void main(String[] args) {
		int[] arr = {4, 10, 3, 5, 1};
		heapSort(arr, 5);
		System.out.println(java.util.Arrays.toString(arr));
	}
}
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)

def heap_sort(arr):
    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)

arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print(arr)
#include <stdio.h>
void swapv(int *a, int *b) { int t = *a; *a = *b; *b = t; }
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) { swapv(&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--) { swapv(&arr[0], &arr[i]); heapify(arr, i, 0); }
}
int main() {
	int arr[] = {4, 10, 3, 5, 1};
	heapSort(arr, 5);
	for (int i = 0; i < 5; i++) printf("%d ", arr[i]);
	return 0;
}

Step by Step

Heap बनाना और इसका maximum हटाना दोनों उसी 'sift down' operation से किए जाते हैं: root हटाने के बाद, आखिरी element इसकी जगह लेता है और इसके बड़े child के साथ नीचे की ओर swap होता रहता है जब तक heap property restore न हो जाए।

उदाहरण: Step by Step

#include <iostream>
using namespace std;
int main() {
	cout << "Build max heap first, then repeatedly swap root (max) to the end and sift down the reduced heap";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Build max heap first, then repeatedly swap root (max) to the end and sift down the reduced heap");
	}
}
print("Build max heap first, then repeatedly swap root (max) to the end and sift down the reduced heap")
#include <stdio.h>
int main() {
	printf("Build max heap first, then repeatedly swap root (max) to the end and sift down the reduced heap");
	return 0;
}

Small Array

[4, 10, 3, 5, 1] जैसे एक छोटे array पर heap sort trace करना initial heap-building phase के बाद repeated root-removal steps दिखाता है, हर एक heap को एक से छोटा करते हुए और array के आखिर में sorted हिस्से को बढ़ाते हुए।

उदाहरण: Small Array

#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};
	for (int i = 1 / 2 - 1; i >= 0; i--) heapify(arr, 5, i);
	heapify(arr, 5, 0);
	for (int x : arr) cout << x << " ";
	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};
		heapify(arr, 5, 0);
		System.out.println(java.util.Arrays.toString(arr));
	}
}
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]
heapify(arr, 5, 0)
print(arr)
#include <stdio.h>
void swapv(int *a, int *b) { int t = *a; *a = *b; *b = t; }
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) { swapv(&arr[i], &arr[largest]); heapify(arr, n, largest); }
}
int main() {
	int arr[] = {4, 10, 3, 5, 1};
	heapify(arr, 5, 0);
	for (int i = 0; i < 5; i++) printf("%d ", arr[i]);
	return 0;
}

Practice

Merge sort के विपरीत, heap sort को किसी extra array की ज़रूरत नहीं — heap और बढ़ता sorted region दोनों original array के अंदर ही रहते हैं, यही कारण है कि heap sort को memory tight होने पर value दी जाती है भले ही यह practice में एक well-tuned quicksort से आमतौर पर थोड़ा धीमा हो।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Unlike merge sort, heap sort needs no extra array; the heap and sorted region share the original array";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Unlike merge sort, heap sort needs no extra array; the heap and sorted region share the original array");
	}
}
print("Unlike merge sort, heap sort needs no extra array; the heap and sorted region share the original array")
#include <stdio.h>
int main() {
	printf("Unlike merge sort, heap sort needs no extra array; the heap and sorted region share the original array");
	return 0;
}

Summary

Heap sort हर case में O(n log n) time की गारंटी देता है, सिर्फ O(1) extra space के साथ, इसे merge sort के guaranteed time (लेकिन extra memory) और quicksort की average speed (लेकिन worst-case risk) के बीच एक reliable middle ground बनाते हुए।

उदाहरण: Summary

#include <iostream>
using namespace std;
int main() {
	cout << "Heap sort: guaranteed O(n log n) time with only O(1) extra space";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Heap sort: guaranteed O(n log n) time with only O(1) extra space");
	}
}
print("Heap sort: guaranteed O(n log n) time with only O(1) extra space")
#include <stdio.h>
int main() {
	printf("Heap sort: guaranteed O(n log n) time with only O(1) extra space");
	return 0;
}
Related Topics

Heap Sort Algorithm क्या है · Quick Sort क्या है · Counting Sort क्या है · Heap परिचय

{# 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. Heap build n / 2 - 1 के बजाय index n - 1 पर शुरू करना, leaves पर अनावश्यक काम करते हुए।
  2. गलत child formulas उपयोग करना, जैसे 2 * i और 2 * i + 1, एक zero-indexed array में।
  3. हर swap के बाद shrinking size के बजाय पूरे size n पर heapify call करना, इसलिए sorted tail disturb होती है।
🔒

Chapter Quiz — Complete all 9 topics to unlock

0/9 topics done

Complete these topics first:

← Previous Lesson Quick Sort Next Lesson → Counting Sort

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.