Dalam tutorial ini, Anda akan mempelajari cara kerja algoritma urutan tumpukan. Selain itu, Anda akan menemukan contoh kerja heap sort di C, C ++, Java dan Python.
Heap Sort adalah algoritme pengurutan yang populer dan efisien dalam pemrograman komputer. Mempelajari cara menulis algoritme pengurutan heap memerlukan pengetahuan tentang dua jenis struktur data - array dan pohon.
Set awal bilangan yang ingin kita urutkan disimpan dalam array misalnya (10, 3, 76, 34, 23, 32)dan setelah pengurutan, kita mendapatkan array yang diurutkan(3,10,23,32,34,76)
Heap sort bekerja dengan memvisualisasikan elemen array sebagai jenis khusus dari pohon biner lengkap yang disebut heap.
Sebagai prasyarat, Anda harus mengetahui tentang pohon biner lengkap dan struktur data heap.
Hubungan antara Indeks Array dan Elemen Pohon
Pohon biner lengkap memiliki properti menarik yang dapat kita gunakan untuk menemukan anak dan orang tua dari simpul mana pun.
Jika indeks dari salah satu elemen dalam array adalah i, elemen dalam indeks 2i+1akan menjadi anak kiri dan elemen dalam 2i+2indeks akan menjadi anak kanan. Juga, induk dari setiap elemen pada indeks i diberikan oleh batas bawah (i-1)/2.
Hubungan antara indeks larik dan heap
Mari kita uji,
Anak kiri 1 (indeks 0) = elemen dalam (2 * 0 + 1) indeks = elemen dalam 1 indeks = 12 Anak kanan 1 = elemen dalam (2 * 0 + 2) indeks = elemen dalam 2 indeks = 9 Demikian pula, Anak kiri 12 (indeks 1) = elemen dalam (2 * 1 + 1) indeks = elemen dalam 3 indeks = 5 Anak kanan 12 = elemen dalam (2 * 1 + 2) indeks = elemen dalam 4 indeks = 6
Mari kita juga mengkonfirmasi bahwa aturan berlaku untuk menemukan induk dari sembarang simpul
Induk dari 9 (posisi 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 Induk dari 12 (posisi 1) = (1-1) / 2 = 0 indeks = 1
Memahami pemetaan indeks larik ke posisi pohon ini sangat penting untuk memahami cara kerja Struktur Data Heap dan cara menggunakannya untuk mengimplementasikan Urutan Heap.
Apa itu Struktur Data Heap?
Heap adalah struktur data berbasis pohon khusus. Pohon biner dikatakan mengikuti struktur data heap jika
- itu adalah pohon biner lengkap
- Semua node di pohon mengikuti properti bahwa mereka lebih besar dari anak-anaknya, yaitu elemen terbesar ada di root dan kedua anaknya dan lebih kecil dari root dan seterusnya. Heap seperti ini disebut max-heap. Jika sebaliknya, semua node lebih kecil dari anak-anaknya, ini disebut min-heap
Diagram contoh berikut memperlihatkan Max-Heap dan Min-Heap.
Max Heap dan Min Heap
Untuk mempelajari lebih lanjut tentang itu, silakan kunjungi Struktur Data Heap.
Cara "menumpuk" pohon
Mulai dari pohon biner lengkap, kita dapat memodifikasinya menjadi Max-Heap dengan menjalankan fungsi yang disebut heapify pada semua elemen non-daun dari heap.
Karena heapify menggunakan rekursi, ini bisa jadi sulit dipahami. Jadi, pertama-tama mari pikirkan tentang bagaimana Anda akan menumpuk pohon hanya dengan tiga elemen.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify base case
Contoh di atas menunjukkan dua skenario - satu di mana root adalah elemen terbesar dan kita tidak perlu melakukan apa pun. Dan satu lagi di mana root memiliki elemen yang lebih besar sebagai anak dan kami perlu menukar untuk mempertahankan properti max-heap.
Jika Anda bekerja dengan algoritme rekursif sebelumnya, Anda mungkin telah mengidentifikasi bahwa ini pasti kasus dasarnya.
Sekarang mari kita pikirkan skenario lain di mana terdapat lebih dari satu level.
Cara menumpuk elemen root saat subpohonnya sudah menjadi tumpukan maksimum
Elemen teratas bukanlah max-heap tetapi semua sub-tree adalah max-heap.
Untuk mempertahankan properti max-heap untuk seluruh pohon, kita harus terus menekan 2 ke bawah hingga mencapai posisi yang benar.
Cara menumpuk elemen root ketika subpohonnya adalah tumpukan maksimal
Jadi, untuk mempertahankan properti max-heap di pohon di mana kedua sub-pohon adalah max-heap, kita perlu menjalankan heapify pada elemen root berulang kali hingga lebih besar dari anak-anaknya atau menjadi simpul daun.
Kita bisa menggabungkan kedua kondisi ini dalam satu fungsi heapify sebagai
void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) )
Fungsi ini berfungsi untuk kasus dasar dan pohon dengan berbagai ukuran. Dengan demikian, kita dapat memindahkan elemen root ke posisi yang benar untuk mempertahankan status max-heap untuk ukuran pohon apa pun selama sub-pohon adalah max-heap.
Bangun max-heap
Untuk membangun max-heap dari pohon mana pun, kita dapat mulai menumpuk setiap sub-pohon dari bawah ke atas dan berakhir dengan max-heap setelah fungsi diterapkan ke semua elemen termasuk elemen root.
Dalam kasus pohon lengkap, indeks pertama dari simpul non-daun diberikan oleh n/2 - 1. Semua node lain setelah itu adalah node daun dan karenanya tidak perlu di-heapifikasi.
Jadi, kami dapat membangun heap maksimum sebagai
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Buat array dan hitung i 
Langkah-langkah membangun heap maks untuk penyortiran heap 
Langkah-langkah membangun heap maks untuk penyortiran heap 
Langkah-langkah membangun heap maks untuk penyortiran heap
Seperti yang ditunjukkan pada diagram di atas, kita mulai dengan menumpuk pohon terkecil dan secara bertahap naik hingga mencapai elemen akar.
Jika Anda telah memahami semuanya sampai di sini, selamat, Anda sedang dalam perjalanan untuk menguasai jenis Heap.
Bagaimana Heap Sort Bekerja?
- Karena pohon memenuhi properti Max-Heap, maka item terbesar disimpan di simpul akar.
- Swap: Hapus elemen root dan letakkan di akhir array (posisi ke-n) Letakkan item terakhir dari pohon (heap) di tempat kosong.
- Hapus: Mengurangi ukuran tumpukan sebanyak 1.
- Heapify: Heapify elemen root lagi sehingga kita memiliki elemen tertinggi di root.
- Proses ini diulangi sampai semua item dari daftar diurutkan.
Tukar, Hapus, dan Heapify
Kode di bawah menunjukkan operasi.
// Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); )
Contoh Python, Java dan C / C ++
Python Java C ++ # Heap Sort in python def heapify(arr, n, i): # Find largest among root and children largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r # If root is not largest, swap with largest and continue heapifying if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build max heap for i in range(n//2, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): # Swap arr(i), arr(0) = arr(0), arr(i) # Heapify root element heapify(arr, i, 0) arr = (1, 12, 9, 5, 6, 10) heapSort(arr) n = len(arr) print("Sorted array is") for i in range(n): print("%d " % arr(i), end='')
// Heap Sort in Java public class HeapSort ( public void sort(int arr()) ( int n = arr.length; // Build max heap for (int i = n / 2 - 1; i>= 0; i--) ( heapify(arr, n, i); ) // Heap sort for (int i = n - 1; i>= 0; i--) ( int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // Heapify root element heapify(arr, i, 0); ) ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l arr(largest)) largest = l; if (r arr(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int swap = arr(i); arr(i) = arr(largest); arr(largest) = swap; heapify(arr, n, largest); ) ) // Function to print an array 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 code public static void main(String args()) ( int arr() = ( 1, 12, 9, 5, 6, 10 ); HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); ) )
// Heap Sort in C #include // Function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) ) // Main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) printf("%d ", arr(i)); printf(""); ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); printf("Sorted array is "); printArray(arr, n); )
// Heap Sort in C++ #include using namespace std; void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(arr(i), arr(largest)); heapify(arr, n, largest); ) ) // main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(arr(0), arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) cout << arr(i) << " "; cout << ""; ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); cout << "Sorted array is "; printArray(arr, n); )
Kompleksitas Urutan Heap
Urutan Heap memiliki O(nlog n)kerumitan waktu untuk semua kasus (kasus terbaik, kasus rata-rata, dan kasus terburuk).
Mari kita pahami alasannya. Tinggi pohon biner lengkap yang mengandung n elemen adalahlog n
As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.
In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.
Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.
Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.
Heap Sort Applications
Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort's running time and constant O(1) upper bound on its auxiliary storage.
Meskipun Heap Sort memiliki O(n log n)kerumitan waktu bahkan untuk kasus terburuk, ia tidak memiliki lebih banyak aplikasi (dibandingkan dengan algoritme pengurutan lain seperti Quick Sort, Merge Sort). Namun, struktur datanya yang mendasarinya, heap, dapat digunakan secara efisien jika kita ingin mengekstrak yang terkecil (atau terbesar) dari daftar item tanpa biaya tambahan untuk menyimpan item yang tersisa dalam urutan yang diurutkan. Misalnya Antrian Prioritas.
