Heap sort bouwt een binary heap uit de array, haalt vervolgens herhaaldelijk het maximum uit om gesorteerde volgorde te produceren. Het draait in O(n log n) en is in-place.
Een max-heap houdt het grootste element aan de wortel. Bouw de heap (O(n)), verwissel vervolgens de wortel naar het einde, verklein de heap en herpelletiseer (sift down) — n keer.
import heapq
def heap_sort(arr):
heapq.heapify(arr) # min-heap in O(n)
return [heapq.heappop(arr) # pop smallest n times
for _ in range(len(arr))]
heap_sort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
Een klassieke implementatie doet het in plaats door sift down binnen de array.
Gebruik wanneer u guaranteed O(n log n) en O(1) extra geheugen nodig hebt (merge sort heeft O(n) nodig; quicksort riskeert O(n²)). Het is niet stabiel en heeft slechte cache-lokaliteit, dus het is in de praktijk vaak langzamer dan quicksort. Dezelfde heap ondersteunt priority queues en het zoeken naar de top-k elementen.
Heap sort is de enige veelgebruikte sort die zowel worst-case O(n log n) als in-place is, waardoor het waardevol is in geheugen-beperkte of gegarandeerde instellingen.
De heap-structuur eronder is breed nuttig — priority queues, Dijkstra's algoritme en streaming top-k.
Het verankert het idee dat de juiste gegevensstructuur een algoritme efficiënt maakt.
Een bibliotheek met IT-sollicitatievragen met gedetailleerde antwoorden — van Junior tot Senior.
Doneren