Šajā apmācībā jūs uzzināsiet, kā darbojas kaudzes šķirošanas algoritms. Jūs atradīsit arī kaudzes kārtošanas piemērus C, C ++, Java un Python.
Heap Sort ir populārs un efektīvs šķirošanas algoritms datorprogrammēšanā. Lai uzzinātu, kā rakstīt kaudzes šķirošanas algoritmu, ir nepieciešamas divu veidu datu struktūru zināšanas - masīvi un koki.
Sākotnējais skaitļu kopums, kuru mēs vēlamies kārtot, tiek glabāts masīvā, piemēram, (10, 3, 76, 34, 23, 32)un pēc šķirošanas mēs iegūstam sakārtotu masīvu(3,10,23,32,34,76)
Kupu šķirošana darbojas, vizualizējot masīva elementus kā īpaša veida pilnīgu bināro koku, ko sauc par kaudzi.
Kā priekšnoteikums jums jāzina par pilnīgu bināro koku un kaudzes datu struktūru.
Masīvu indeksu un koku elementu saistība
Pilnīgam bināram kokam ir interesanta īpašība, kuru mēs varam izmantot, lai atrastu jebkura mezgla bērnus un vecākus.
Ja jebkura masīva elementa indekss ir i, indeksa elements 2i+1kļūs par kreiso bērnu un 2i+2indeksa elements kļūs par pareizo bērnu. Arī jebkura indeksa i elementa vecāku i indeksā izsaka (i-1)/2.
Saistība starp masīva un kaudzes indeksiem
Pārbaudīsim to,
1 kreisais bērns (indekss 0) = elements (2 * 0 + 1) indeksā = elements 1 indeksā = 12 Labais 1 bērns = elements (2 * 0 + 2) indeksā = elements 2 indeksā = 9 Līdzīgi, Kreisais 12 bērnu bērns (indekss 1) = elements (2 * 1 + 1) indeksā = elements 3 indeksā = 5 Labais 12 bērnu bērns = elements (2 * 1 + 2) indeksā = elements 4 indeksā = 6
Apstiprināsim arī to, ka noteikumi attiecas uz jebkura mezgla vecāku atrašanu
Vecāks no 9 (2. pozīcija) = (2-1) / 2 = ½ = 0.5 ~ 0 indekss = 1 Vecāks no 12 (1. pozīcija) = (1-1) / 2 = 0 indekss = 1
Izpratne par šo masīvu indeksu kartēšanu ar koku pozīcijām ir kritiska, lai saprastu, kā darbojas kaudzes datu struktūra un kā to izmanto, lai ieviestu kaudzes kārtošanu.
Kas ir kaudzes datu struktūra?
Kaudze ir īpaša uz kokiem balstīta datu struktūra. Tiek teikts, ka binārs koks seko kaudzes datu struktūrai, ja
- tas ir pilnīgs binārs koks
- Visi koka mezgli seko īpašībai, ka tie ir lielāki par viņu bērniem, ti, lielākais elements ir pie saknes un abiem tā bērniem, un mazāks par sakni utt. Šādu kaudzi sauc par max-kaudzi. Ja tā vietā visi mezgli ir mazāki par viņu bērniem, to sauc par min-kaudzi
Šajā diagrammā ir parādīts Max-Heap un Min-Heap.
Maks Heap un Min Heap
Lai uzzinātu vairāk par to, lūdzu, apmeklējiet kaudzes datu struktūru.
Kā koku "uzkrāt"
Sākot no pilnīga binārā koka, mēs to varam pārveidot, lai kļūtu par Max-Heap, izpildot funkciju, ko sauc par heapify, uz visiem kaudzes elementiem, kas nav lapu lapas.
Tā kā heapify izmanto rekursiju, to var būt grūti aptvert. Tāpēc vispirms padomāsim, kā jūs varētu uzkrāt koku tikai ar trim elementiem.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Papildināt bāzes gadījumus
Iepriekš minētajā piemērā parādīti divi scenāriji - viens, kurā sakne ir lielākais elements, un mums nekas nav jādara. Un vēl viens, kurā saknei bērnībā bija lielāks elements, un mums vajadzēja nomainīt, lai saglabātu max-heap īpašību.
Ja iepriekš esat strādājis ar rekursīviem algoritmiem, jūs droši vien esat noteicis, ka tam ir jābūt pamata gadījumam.
Tagad domāsim par citu scenāriju, kurā ir vairāk nekā viens līmenis.
Kā saknīt saknes elementu, kad tā apakškoki jau ir maksimāli kaudzīti
Augšējais elements nav max-kaudze, bet visi apakškoki ir max-kaudzes.
Lai saglabātu max-heap īpašību visam kokam, mums būs jāturpina virzīt 2 uz leju, līdz tas sasniedz pareizo stāvokli.
Kā saknīt saknes elementu, ja tā apakškoki ir maksimāli daudz
Tādējādi, lai saglabātu max-heap īpašību kokā, kur abi apakškoki ir max-kaudzes, mums atkārtoti jāskrien ar saknes elementu, līdz tas ir lielāks par tā bērniem vai tas kļūst par lapu mezglu.
Abus šos nosacījumus mēs varam apvienot vienā uzkrājošajā funkcijā kā
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); ) )
Šī funkcija darbojas gan pamata gadījumā, gan jebkura izmēra kokam. Tādējādi mēs varam pārvietot saknes elementu pareizajā pozīcijā, lai saglabātu max-heap statusu jebkuram koku izmēram, kamēr apakškoki ir max-kaudzes.
Veidot max-kaudzi
Lai izveidotu maksimālo kaudzi no jebkura koka, mēs varam sākt krāt katru apakškoku no apakšas uz augšu un galu galā ar maksimālo kaudzi pēc tam, kad funkcija ir piemērota visiem elementiem, ieskaitot saknes elementu.
Pilnīga koka gadījumā mezglu bez lapas pirmo indeksu norāda n/2 - 1. Visi pārējie mezgli pēc tam ir lapu mezgli, un tāpēc tie nav jākrāj.
Tātad, mēs varam izveidot maksimālu kaudzi kā
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Izveidojiet masīvu un aprēķiniet i 
Soļi, lai izveidotu maksimālu kaudzi 
kaudzes kārtošanai 
Soļi, lai izveidotu maksimālu kaudzi kaudzes kārtošanai
Kā parādīts iepriekšējā diagrammā, mēs sākam ar zemāko mazāko koku krāšanu un pakāpeniski virzāmies uz augšu, līdz sasniedzam saknes elementu.
Ja līdz šim esat visu sapratis, apsveicu, jūs esat ceļā, lai apgūtu kaudzes veidu.
Kā darbojas kaudzes kārtošana?
- Tā kā koks apmierina rekvizītu Max-Heap, lielākais vienums tiek glabāts saknes mezglā.
- Apmainīt: noņemiet saknes elementu un ielieciet masīva galā (n-tā pozīcija). Koka pēdējo kaudzi (kaudzi) ielieciet brīvajā vietā.
- Noņemt: Samaziniet kaudzes lielumu par 1.
- Heapify: vēlreiz palieliniet saknes elementu, lai mums saknē būtu visaugstākais elements.
- Process tiek atkārtots, līdz visi saraksta vienumi ir sakārtoti.
Apmainiet, noņemiet un palieliniet
Zemāk redzamais kods parāda darbību.
// 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); )
Python, Java un C / C ++ piemēri
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); )
Kaudžu kārtošanas sarežģītība
Heap Sort ir O(nlog n)laika sarežģītība visiem gadījumiem (labākais gadījums, vidējais gadījums un sliktākais gadījums).
Ļaujiet mums saprast iemeslu. Pilnīga binārā koka, kas satur n elementus, augstums irlog 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.
Kaut arī Heap Sort ir O(n log n)sarežģītāks laiks pat sliktākajā gadījumā, tam nav vairāk lietojumprogrammu (salīdzinot ar citiem šķirošanas algoritmiem, piemēram, Quick Sort, Merge Sort). Tomēr tās pamatā esošo datu struktūru, kaudzi, var efektīvi izmantot, ja mēs vēlamies iegūt mazāko (vai lielāko) no vienumu saraksta bez papildu izmaksām, saglabājot atlikušos priekšmetus sakārtotajā secībā. Piemēram, prioritārajām rindām.
