Hrúguröðun
Útlit
Hrúguröðun er röðunarreiknirit sem velur ákveðið stak stærsta (eða minnsta) og raðar því aftast(eða fremst) í lista. Næstu stök sem eru lesinn í listan eru síðan röðuð annað hvort fyrir framan eða aftan upphaflega valda stakið, eftir því sem við á.
Hrúguröðun er aðeins hægari en vel útfærð snarröðun en hefur forskot í versta tilviks, tilvikum þar hún þarf bara O(n log n) tíma til að ljúka keyrslu.
Sauðakóði
[breyta | breyta frumkóða]Einfaldur sauðakóðu fyrir reikniritið, takið eftir að allir listar eru zero based.
function heapSort(a, count) is input: an unordered array a of length count (first place a in max-heap order) heapify(a, count) end := count - 1 while end > 0 do (swap the root(maximum value) of the heap with the last element of the heap) swap(a[end], a[0]) (decrease the size of the heap by one so that the previous max value will stay in its proper placement) end := end - 1 (put the heap back in max-heap order) siftDown(a, 0, end) function heapify(a,count) is (start is assigned the index in a of the last parent node) start := (count - 1) / 2 while start ≥ 0 do (sift down the node at index start to the proper place such that all nodes below the start index are in heap order) siftDown(a, start, count-1) start := start - 1 (after sifting down the root all nodes/elements are in heap order) function siftDown(a, start, end) is input: end represents the limit of how far down the heap to sift. root := start
while root * 2 + 1 ≤ end do (While the root has at least one child) child := root * 2 + 1 (root*2+1 points to the left child) (If the child has a sibling and the child's value is less than its sibling's...) if child < end and a[child] < a[child + 1] then child := child + 1 (... then point to the right child instead) if a[root] < a[child] then (out of max-heap order) swap(a[root], a[child]) root := child (repeat to continue sifting down the child now) else return
Heimildir
[breyta | breyta frumkóða]- Java sýnidæmi um hvernig hrúguröðun virkar Geymt 19 janúar 2009 í Wayback Machine
- Heapsort code