Heap sort a thógann bínshraith dhúbailte (binary heap) ó an eagar, agus ansin tarraingíonn sé an uachtar arís is arís eile chun ordú sórtáilte a tháirgeadh. Rith sé ar O(n log n) agus tá sé in-áit.
Coimeádann max-heap an eilimint is mó ag an fhréamh. Tóg an heap (O(n)), ansin malartaigh an fréamh go dtí an deireadh, laghdaigh an heap, agus athfheidhm ar an spréacharnach (sift down) — n huaire.
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]
Déanann feidhmiú clasaiceach é in-áit trí sift down a dhéanamh laistigh den eagar.
Úsáid nuair a bhíonn do dhíth O(n log n) ráthaithe agus cuimhne bhreise O(1) ort (tá O(n) de dhíth ar merge sort ; baol O(n²) a bheith ar quicksort). Níl sé cobhsaí agus tá drochúsáid cache aige, mar sin is minic a bhíonn sé níos moille i ndáiríre ná quicksort. Soláthaíonn an fhianchuimhne chéanna scuainí tosaíochta agus aimsiú na n-eilimintí top-k.
Is é heap sort an t-aon sórt coitianta atá ina O(n log n) ar an chás is tubaisteach agus in-áit, rud a dhéanann luachmhar é i socrú teoranta cuimhne nó teoranta.
Tá an struchtúr heap thíos an-úsáideach — scuainí tosaíochta, algartam Dijkstra, agus top-k i sruth.
Soláthraíonn sé an smaoineamh go ndéanann an struchtúr sonraí ceart algartam éifeachtach.