Hrúguröðun

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ð á.

Hreyfimynd sem sýnir hvernig hrúguröðun virkar

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

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

• Java sýnidæmi um hvernig hrúguröðun virkar Geymt 19 janúar 2009 í Wayback Machine
• Heapsort code