Fara í innihald

Hrúguröðun

Úr Wikipediu, frjálsa alfræðiritinu
Hreyfimynd sem sýnir hvernig hrúguröðun virkar

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