În acest tutorial, veți afla cum funcționează algoritmul de sortare heap. De asemenea, veți găsi exemple de lucru de tip heap în C, C ++, Java și Python.
Heap Sort este un algoritm de sortare popular și eficient în programarea computerelor. Învățarea modului de scriere a algoritmului de sortare heap necesită cunoașterea a două tipuri de structuri de date - matrice și copaci.
Setul inițial de numere pe care dorim să le sortăm este stocat într-o matrice, de exemplu (10, 3, 76, 34, 23, 32)și după sortare, obținem o matrice sortată(3,10,23,32,34,76)
Sortarea Heap funcționează prin vizualizarea elementelor matricei ca un tip special de arbore binar complet numit heap.
Ca o condiție prealabilă, trebuie să știți despre un arbore binar complet și o structură de date heap.
Relația dintre indexurile matricei și elementele arborelui
Un copac binar complet are o proprietate interesantă pe care o putem folosi pentru a găsi copiii și părinții oricărui nod.
Dacă indexul oricărui element din matrice este i, elementul din index 2i+1va deveni copilul stâng și elementul din 2i+2index va deveni copilul potrivit. De asemenea, părintele oricărui element de la indexul i este dat de limita inferioară a (i-1)/2.
Relația dintre indicii matrice și heap
Să testăm,
Copilul stâng al 1 (index 0) = element în (2 * 0 + 1) index = element în 1 index = 12 Fig. Dreapta al 1 = element în (2 * 0 + 2) index = element în 2 index = 9 În mod similar, Copil stâng de 12 (index 1) = element în (2 * 1 + 1) index = element în 3 index = 5 Copil drept din 12 = element în (2 * 1 + 2) index = element în 4 index = 6
Să confirmăm, de asemenea, că regulile sunt valabile pentru găsirea părintelui oricărui nod
Părinte de 9 (poziția 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Părinte de 12 (poziția 1) = (1-1) / 2 = 0 index = 1
Înțelegerea acestei mapări a indexurilor matrice în pozițiile arborelui este esențială pentru înțelegerea modului în care funcționează structura de date Heap și modul în care este utilizată pentru a implementa sortarea Heap.
Ce este structura de date Heap?
Heap este o structură specială de date bazată pe copaci. Se spune că un arbore binar urmează o structură de date heap dacă
- este un arbore binar complet
- Toate nodurile din copac urmează proprietatea că sunt mai mari decât copiii lor, adică cel mai mare element este la rădăcină și atât copiii săi, cât și mai mici decât rădăcina și așa mai departe. O astfel de heap se numește max-heap. Dacă, în schimb, toate nodurile sunt mai mici decât copiii lor, se numește min-heap
Următorul exemplu de diagramă arată Max-Heap și Min-Heap.
Max Heap și Min Heap
Pentru a afla mai multe despre aceasta, vă rugăm să vizitați Heap Data Structure.
Cum să „heapify” un copac
Pornind de la un arbore binar complet, îl putem modifica pentru a deveni un Max-Heap executând o funcție numită heapify pe toate elementele care nu sunt frunze ale heap-ului.
Deoarece heapify utilizează recursivitatea, poate fi dificil de înțeles. Deci, să ne gândim mai întâi la modul în care ați heapify un copac cu doar trei elemente.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify cazuri de bază
Exemplul de mai sus prezintă două scenarii - unul în care rădăcina este cel mai mare element și nu trebuie să facem nimic. Și altul în care rădăcina avea un element mai mare în copilărie și trebuia să schimbăm pentru a menține proprietatea max-heap.
Dacă ați lucrat anterior cu algoritmi recursivi, probabil ați identificat că acesta trebuie să fie cazul de bază.
Acum să ne gândim la un alt scenariu în care există mai mult de un nivel.
Cum să heapify element rădăcină atunci când subarborii săi sunt deja maxim grămezi
Elementul de sus nu este un heap-max, dar toți sub-copacii sunt heap-max.
Pentru a menține proprietatea max-heap pentru întregul copac, va trebui să continuăm să împingem 2 în jos până când acesta atinge poziția corectă.
Cum să heapify elementul rădăcină atunci când subarborii săi sunt maximi
Astfel, pentru a menține proprietatea max-heap într-un copac în care ambii sub-copaci sunt max-grămezi, trebuie să rulăm heapify pe elementul rădăcină în mod repetat până când acesta este mai mare decât copiii săi sau devine un nod frunză.
Putem combina ambele condiții într-o singură funcție de heapify
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); ) )
Această funcție funcționează atât pentru carcasa de bază, cât și pentru un copac de orice dimensiune. Putem astfel muta elementul rădăcină în poziția corectă pentru a menține starea max-heap pentru orice dimensiune de copac, atâta timp cât sub-copacii sunt max-heap.
Construiți max-heap
Pentru a construi un max-heap din orice copac, putem începe astfel să heapifying fiecare sub-copac de jos în sus și să sfârșim cu un max-heap după ce funcția este aplicată tuturor elementelor, inclusiv elementului rădăcină.
În cazul unui arbore complet, primul index al unui nod non-frunză este dat de n/2 - 1. Toate celelalte noduri după aceea sunt noduri frunze și, prin urmare, nu trebuie să fie heapified.
Deci, putem construi o grămadă maximă ca
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Creați matrice și calculați i 
Pași pentru a construi heap maxim pentru sortare heap 
Pași pentru a construi heap maxim pentru sortare heap 
Pași pentru a construi heap maxim pentru sortare heap
Așa cum se arată în diagrama de mai sus, începem prin adunarea celor mai mici copaci și ne deplasăm treptat în sus până ajungem la elementul rădăcină.
Dacă ai înțeles totul până aici, felicitări, ești pe cale să stăpânești sortul Heap.
Cum funcționează sortarea în grămadă?
- Deoarece arborele satisface proprietatea Max-Heap, atunci cel mai mare element este stocat la nodul rădăcină.
- Swap: Scoateți elementul rădăcină și puneți-l la sfârșitul matricei (poziția a n-a) Puneți ultimul element al arborelui (heap) în locul liber.
- Eliminați: reduceți dimensiunea grămezii cu 1.
- Heapify: Heapify din nou elementul rădăcină, astfel încât să avem cel mai înalt element la rădăcină.
- Procesul se repetă până când toate elementele din listă sunt sortate.
Schimbați, eliminați și Heapify
Codul de mai jos arată operațiunea.
// 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); )
Exemple Python, Java și 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); )
Complexitate sortare grămadă
Heap Sort are O(nlog n)complexități de timp pentru toate cazurile (cel mai bun caz, cazul mediu și cel mai rău caz).
Să înțelegem motivul pentru care. Înălțimea unui arbore binar complet care conține n elemente estelog 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.
Deși Heap Sort are O(n log n)complexitate de timp chiar și în cel mai rău caz, nu are mai multe aplicații (comparativ cu alți algoritmi de sortare precum Sortare rapidă, Sortare Merge). Cu toate acestea, structura sa subiacentă de date, heap, poate fi utilizată în mod eficient dacă dorim să extragem cel mai mic (sau cel mai mare) din lista de articole fără cheltuielile generale de a păstra restul articolelor în ordinea sortată. De exemplu cozile prioritare.
