Dalam tutorial ini, anda akan belajar bagaimana algoritma pengumpulan timbunan berfungsi. Anda juga akan mendapat contoh contoh timbunan yang berfungsi di C, C ++, Java dan Python.
Heap Sort adalah algoritma penyortiran yang popular dan cekap dalam pengaturcaraan komputer. Mempelajari cara menulis algoritma pengumpulan timbunan memerlukan pengetahuan mengenai dua jenis struktur data - tatasusunan dan pokok.
Kumpulan nombor awal yang ingin kami urutkan disimpan dalam array contohnya (10, 3, 76, 34, 23, 32)dan setelah menyusun, kami mendapat susunan yang disusun(3,10,23,32,34,76)
Jenis timbunan berfungsi dengan memvisualisasikan unsur larik sebagai sejenis pokok binari lengkap yang dipanggil timbunan.
Sebagai prasyarat, anda mesti mengetahui mengenai struktur data biner dan timbunan lengkap.
Hubungan antara Indeks Array dan Unsur Pokok
Pokok binari yang lengkap mempunyai harta yang menarik yang boleh kita gunakan untuk mencari anak-anak dan ibu bapa mana-mana nod.
Sekiranya indeks unsur dalam array adalah i, elemen dalam indeks 2i+1akan menjadi anak kiri dan elemen dalam 2i+2indeks akan menjadi anak kanan. Juga, induk bagi mana-mana elemen pada indeks i diberikan oleh batas bawah (i-1)/2.
Hubungan antara indeks array dan timbunan
Mari kita mengujinya,
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 Begitu juga, 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
Marilah kita juga mengesahkan bahawa peraturan tersebut berlaku untuk mencari ibu bapa sebarang nod
Ibu bapa 9 (kedudukan 2) = (2-1) / 2 = ½ = 0.5 ~ 0 indeks = 1 Ibu bapa 12 (kedudukan 1) = (1-1) / 2 = 0 indeks = 1
Memahami pemetaan indeks array ke kedudukan pokok sangat penting untuk memahami bagaimana Struktur Data Heap berfungsi dan bagaimana ia digunakan untuk melaksanakan Urutan Heap.
Apakah Struktur Data Tumpukan?
Heap adalah struktur data berasaskan pokok khas. Pokok binari dikatakan mengikuti struktur data timbunan jika
- ia adalah pokok binari yang lengkap
- Semua simpul di pokok mengikuti sifat yang lebih besar daripada anak-anaknya iaitu unsur terbesar berada pada akar dan kedua-dua anaknya dan lebih kecil daripada akar dan sebagainya. Tumpukan semacam itu disebut timbunan maksimum. Sekiranya sebaliknya, semua nod lebih kecil daripada anak-anak mereka, ia dipanggil timbunan min
Contoh rajah berikut menunjukkan Max-Heap dan Min-Heap.
Max Heap dan Min Heap
Untuk mengetahui lebih lanjut mengenainya, sila kunjungi Heap Data Structure.
Cara "mengumpul" pokok
Bermula dari pohon binari yang lengkap, kita dapat mengubahnya menjadi Max-Heap dengan menjalankan fungsi yang disebut heapify pada semua elemen timbunan tanpa daun.
Oleh kerana heapify menggunakan rekursi, sukar untuk dipahami. Oleh itu, mari kita fikirkan terlebih dahulu bagaimana anda akan mengumpulkan sebatang pokok dengan hanya tiga unsur.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Selesaikan kes asas
Contoh di atas menunjukkan dua senario - satu di mana akarnya adalah elemen terbesar dan kita tidak perlu melakukan apa-apa. Dan satu lagi di mana akarnya mempunyai elemen yang lebih besar ketika masih kecil dan kita perlu menukar untuk mengekalkan harta tumpukan maksimum.
Sekiranya anda menggunakan algoritma rekursif sebelumnya, anda mungkin telah mengenal pasti bahawa ini mesti menjadi asas.
Sekarang mari kita fikirkan senario lain di mana terdapat lebih daripada satu tahap.
Cara mengumpul unsur akar apabila subtitanya sudah banyak timbunan
Unsur teratas bukan timbunan maksimum tetapi semua sub-pokok adalah timbunan maksimum.
Untuk mengekalkan harta timbunan maksimum untuk keseluruhan pokok, kita harus terus menekan 2 ke bawah sehingga mencapai kedudukan yang betul.
Cara mengumpul unsur akar apabila subtitrenya adalah timbunan maksimum
Oleh itu, untuk mengekalkan harta timbunan maksimum di pohon di mana kedua-dua sub-pokok adalah tumpukan maksimum, kita perlu menjalankan heapify pada elemen akar berulang kali sehingga lebih besar daripada anak-anaknya atau menjadi simpul daun.
Kita dapat menggabungkan kedua-dua syarat 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 casing asas dan untuk pokok dengan ukuran apa pun. Oleh itu, kita dapat memindahkan elemen akar ke kedudukan yang betul untuk mengekalkan status timbunan maksimum untuk ukuran pokok apa pun selagi sub-pokok adalah timbunan maksimum.
Bina timbunan maksimum
Untuk membina timbunan maksimum dari pokok mana pun, kita dapat mulai mengumpulkan setiap sub-pohon dari bawah ke atas dan berakhir dengan timbunan maksimum setelah fungsi diterapkan pada semua elemen termasuk elemen akar.
Sekiranya pokok lengkap, indeks pertama simpul bukan daun diberikan oleh n/2 - 1. Semua nod lain selepas itu adalah simpul daun dan dengan itu tidak perlu dikumpulkan.
Jadi, kita dapat membina timbunan maksimum sebagai
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Buat 
susun atur dan hitung i Langkah membina timbunan maksimum untuk pengumpulan timbunan 
Langkah - langkah untuk membina timbunan maksimum untuk pengumpulan timbunan 
Langkah - langkah untuk membina timbunan maksimum untuk pengumpulan timbunan
Seperti yang ditunjukkan dalam rajah di atas, kita mulai dengan menumpuk pokok terkecil yang paling rendah dan secara beransur-ansur bergerak ke atas hingga kita mencapai elemen akar.
Sekiranya anda telah memahami segalanya hingga ke sini, tahniah, anda akan berjaya menguasai Heap semacam.
Bagaimana Susunan Heap Berfungsi?
- Oleh kerana pokok memenuhi harta Max-Heap, maka item terbesar disimpan di simpul akar.
- Tukar: Keluarkan elemen akar dan letakkan di hujung larik (kedudukan ke-9) Letakkan item terakhir pokok (timbunan) di tempat kosong.
- Buang: Kurangkan ukuran timbunan dengan 1.
- Heapify: Heapify elemen root sekali lagi sehingga kita mempunyai elemen tertinggi pada root.
- Proses diulang sehingga semua item dalam senarai disusun.
Tukar, Buang, dan Heapify
Kod 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 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); )
Kerumitan Urutan Tumpukan
Heap Sort mempunyai O(nlog n)kerumitan masa untuk semua kes (kes terbaik, kes rata-rata, dan kes terburuk).
Marilah kita memahami sebab mengapa. Ketinggian pokok binari lengkap yang mengandungi unsur n 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.
Walaupun Heap Sort mempunyai O(n log n)kerumitan waktu walaupun untuk keadaan terburuk, ia tidak mempunyai lebih banyak aplikasi (berbanding algoritma penyortiran lain seperti Quick Sort, Merge Sort). Walau bagaimanapun, struktur datanya yang mendasari, timbunan, dapat digunakan dengan efisien jika kita ingin mengekstrak terkecil (atau terbesar) dari daftar item tanpa overhead untuk menyimpan item yang tersisa dalam urutan yang disusun. Contohnya Baris Keutamaan.
