Heap Sort
Terakhir diperbarui
Heap sort adalah algoritma pengurutan yang memperlakukan array sebagai binary heap. Pertama, algoritma ini membangun max-heap, sehingga elemen terbesar berada di root (indeks 0). Lalu, algoritma ini berulang kali menukar root dengan elemen terakhir yang belum terurut, sehingga nilai maksimum terkunci di tempatnya, dan menurunkan (sift down) root yang baru untuk memulihkan sifat heap. Tekan Putar di atas untuk melihat heap dibangun dan nilai-nilainya diambil.
Heap sort menjamin waktu O(n log n) seperti merge sort, tetapi mengurutkan secara in-place dengan ruang tambahan hanya O(1). Algoritma ini tidak stabil dan cenderung punya perilaku cache yang lebih buruk daripada quicksort, jadi sering dipilih saat batas yang terjamin dan memori konstan sama-sama penting.
Kompleksitas waktu dan ruang
| Kasus | Kompleksitas | Catatan |
|---|---|---|
| Kasus terbaik | O(n log n) | Pembangunan + n pengambilan |
| Kasus rata-rata | O(n log n) | Urutan acak |
| Kasus terburuk | O(n log n) | Terjamin |
| Ruang | O(1) | In-place |
| Stabil | Tidak | Sift-down mengubah urutan elemen yang sama |
Langkah demi langkah
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Bangun max-heap dari array (sift down mulai dari induk terakhir). |
| 2 | Tukar root (nilai maksimum) dengan elemen terakhir heap. |
| 3 | Perkecil heap satu elemen: slot terakhir itu kini sudah terurut. |
| 4 | Sift down root yang baru untuk memulihkan sifat max-heap. |
| 5 | Ulangi sampai heap tinggal satu elemen. |
Contoh penerapan
Mengurutkan [3, 1, 6, 5, 2, 4]. Garis | menandai batas antara heap yang menyusut dan bagian akhir yang sudah terurut:
| Putaran | Array | Aksi |
|---|---|---|
| Bangun heap | [6, 5, 4, 1, 2, 3] | Sift down mulai dari induk terakhir untuk membangun max-heap; 6 kini ada di root. |
| 1 | [5, 3, 4, 1, 2 | 6] | Tukar root 6 dengan slot terakhir, perkecil heap, lalu sift down 3. |
| 2 | [4, 3, 2, 1 | 5, 6] | Keluarkan root 5 lewat penukaran, lalu sift down 2 sehingga 4 naik ke root. |
| 3 | [3, 1, 2 | 4, 5, 6] | Keluarkan root 4 lewat penukaran, lalu sift down 1 sehingga 3 naik ke root. |
| 4 | [2, 1 | 3, 4, 5, 6] | Keluarkan root 3 lewat penukaran; 2 sudah memenuhi sifat heap. |
| 5 | [1 | 2, 3, 4, 5, 6] | Keluarkan root 2 lewat penukaran; tersisa satu elemen, jadi array sudah terurut. |
Kapan memakai heap sort
| Pakai saat | Hindari saat |
|---|---|
Kamu butuh kasus terburuk O(n log n) yang terjamin tanpa risiko O(n²). | Kamu butuh pengurutan stabil yang mempertahankan urutan key yang sama. |
Memori terbatas: heap sort mengurutkan secara in-place dengan ruang tambahan hanya O(1). | Performa cache penting dan datanya muat di memori: quicksort biasanya lebih cepat. |
| Kamu sudah memelihara heap (misalnya priority queue) atas datanya. | Kamu ingin perbandingan sesedikit mungkin: merge sort dan quicksort sering melakukan lebih sedikit dalam praktik. |
| Input yang tidak tepercaya bisa memicu kasus terburuk quicksort dan kamu tidak bisa mengacaknya. | Datanya hampir terurut: insertion sort berjalan dalam waktu hampir linear pada data seperti itu. |
Kode Heap Sort
Implementasi Heap Sort yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Heap Sort dalam Python
Python
1def heap_sort(a):2 n = len(a)3 # Build a max-heap, deepest parent first4 for i in range(n // 2 - 1, -1, -1):5 sift_down(a, i, n)6 # Repeatedly move the max to the end and shrink the heap7 for end in range(n - 1, 0, -1):8 a[0], a[end] = a[end], a[0]9 sift_down(a, 0, end)10 return a11
12
13def sift_down(a, i, size):14 while True:15 largest = i16 left, right = 2 * i + 1, 2 * i + 217 if left < size and a[left] > a[largest]:18 largest = left19 if right < size and a[right] > a[largest]:20 largest = right21 if largest == i:22 return23 a[i], a[largest] = a[largest], a[i]24 i = largest25
26
27nums = [12, 11, 13, 5, 6, 7]28print("Before:", nums)29heap_sort(nums)30print("After: ", nums)Kode Heap Sort dalam JavaScript
JavaScript
1function heapSort(a) {2 const n = a.length;3 // Build a max-heap, then repeatedly move the max to the end4 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);5 for (let end = n - 1; end > 0; end--) {6 [a[0], a[end]] = [a[end], a[0]];7 siftDown(a, 0, end);8 }9 return a;10}11
12function siftDown(a, i, size) {13 while (true) {14 const left = 2 * i + 1;15 const right = 2 * i + 2;16 let largest = i;17 if (left < size && a[left] > a[largest]) largest = left;18 if (right < size && a[right] > a[largest]) largest = right;19 if (largest === i) return;20 [a[i], a[largest]] = [a[largest], a[i]];21 i = largest;22 }23}24
25const data = [5, 2, 9, 1, 7, 3];26console.log("Before:", data);27console.log("Sorted:", heapSort([...data]));Kode Heap Sort dalam Java
Java
1import java.util.Arrays;2
3public class Main {4 static void heapSort(int[] arr) {5 int n = arr.length;6 // Build a max-heap, deepest parent first7 for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);8 // Repeatedly move the max to the end and shrink the heap9 for (int end = n - 1; end > 0; end--) {10 swap(arr, 0, end);11 siftDown(arr, 0, end);12 }13 }14
15 static void siftDown(int[] arr, int i, int size) {16 while (true) {17 int largest = i, l = 2 * i + 1, r = 2 * i + 2;18 if (l < size && arr[l] > arr[largest]) largest = l;19 if (r < size && arr[r] > arr[largest]) largest = r;20 if (largest == i) return;21 swap(arr, i, largest);22 i = largest;23 }24 }25
26 static void swap(int[] arr, int a, int b) {27 int tmp = arr[a];28 arr[a] = arr[b];29 arr[b] = tmp;30 }31
32 public static void main(String[] args) {33 int[] arr = {12, 11, 13, 5, 6, 7};34 System.out.println("Before: " + Arrays.toString(arr));35 heapSort(arr);36 System.out.println("After: " + Arrays.toString(arr));37 }38}Kode Heap Sort dalam C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void siftDown(std::vector<int>& a, int n, int i) {11 while (true) {12 int largest = i, l = 2 * i + 1, r = 2 * i + 2;13 if (l < n && a[l] > a[largest]) largest = l;14 if (r < n && a[r] > a[largest]) largest = r;15 if (largest == i) return;16 std::swap(a[i], a[largest]);17 i = largest;18 }19}20
21void heapSort(std::vector<int>& a) {22 int n = static_cast<int>(a.size());23 // Build a max-heap in place24 for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i);25 // Repeatedly move the max to the end and shrink the heap26 for (int end = n - 1; end > 0; --end) {27 std::swap(a[0], a[end]);28 siftDown(a, end, 0);29 }30}31
32int main() {33 std::vector<int> data = {12, 11, 13, 5, 6, 7};34 std::cout << "Before: ";35 printVec(data);36 heapSort(data);37 std::cout << "After: ";38 printVec(data);39 return 0;40}Kode Heap Sort dalam C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void siftDown(int a[], int n, int i) {9 while (1) {10 int largest = i, l = 2 * i + 1, r = 2 * i + 2;11 if (l < n && a[l] > a[largest]) largest = l;12 if (r < n && a[r] > a[largest]) largest = r;13 if (largest == i) return;14 int tmp = a[i];15 a[i] = a[largest];16 a[largest] = tmp;17 i = largest;18 }19}20
21void heapSort(int a[], int n) {22 // Build a max-heap in place23 for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);24 // Repeatedly move the max to the end and shrink the heap25 for (int end = n - 1; end > 0; end--) {26 int tmp = a[0];27 a[0] = a[end];28 a[end] = tmp;29 siftDown(a, end, 0);30 }31}32
33int main(void) {34 int data[] = {12, 11, 13, 5, 6, 7};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 heapSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}FAQ Heap Sort
Berapa kompleksitas waktu heap sort?
Heap sort bernilai
O(n log n) pada kasus terbaik, rata-rata, dan terburuk. Membangun heap bernilai O(n) dan setiap pengambilan dari n pengambilan berbiaya O(log n). Ruang tambahan yang dipakai O(1).Apakah heap sort stabil?
Tidak. Operasi sift-down bisa memindahkan elemen yang sama melewati satu sama lain, jadi heap sort tidak mempertahankan urutan relatif key yang sama.
Kapan sebaiknya memakai heap sort?
Pakai heap sort saat kamu butuh kasus terburuk
O(n log n) yang terjamin dengan memori tambahan hanya O(1). Algoritma ini menghindari risiko O(n²) milik quicksort tanpa buffer O(n) milik merge sort, dengan mengorbankan stabilitas dan performa cache.Apa perbedaan heap sort dan quicksort?
Keduanya mengurutkan secara in-place, tetapi quicksort punya kasus terburuk
O(n²), sedangkan heap sort menjamin O(n log n). Dalam praktik, quicksort biasanya lebih cepat karena lokalitas cache yang lebih baik dan penukaran yang lebih sedikit, jadi heap sort terutama dipilih saat batas kasus terburuk harus terjamin.Apa hubungan heap sort dengan priority queue?
Binary heap adalah implementasi standar priority queue, dan heap sort pada dasarnya adalah mengeluarkan nilai maksimum dari queue itu berulang kali. Jika datamu sudah disimpan di dalam heap, mengambil elemen satu per satu langsung memberimu urutan terurut.
Apakah heap sort butuh max-heap atau min-heap?
Untuk mengurutkan secara naik dan in-place, pakai max-heap: elemen terbesar ditukar ke ujung pada setiap putaran, sehingga bagian akhir yang terurut tumbuh dari kanan. Min-heap akan menghasilkan urutan turun secara in-place, atau urutan naik jika kamu mengambil elemennya ke array terpisah.
Sumber terkait
Visualisasi lainnya
