RosettaCodeData/Task/Sorting-algorithms-Heapsort/00DESCRIPTION

 {{Sorting Algorithm}} {{wikipedia|Heapsort}}
{{omit from|GUISS}}

<br>
[[wp:Heapsort|Heapsort]] is an in-place sorting algorithm with worst case and average complexity of &nbsp; <span style="font-family: serif">O(''n'' log''n'')</span>.

The basic idea is to turn the array into a binary heap structure, which has the property that it allows efficient retrieval and removal of the maximal element.

We repeatedly "remove" the maximal element from the heap, thus building the sorted list from back to front.

Heapsort requires random access, so can only be used on an array-like data structure.

Pseudocode:
 '''function''' heapSort(a, count) '''is'''
    '''input:''' an unordered array ''a'' of length ''count''

    <span style="color: grey">''(first place a in max-heap order)''</span>
    heapify(a, count)

    end := count - 1
    '''while''' end > 0 '''do'''
       <span style="color: grey">''(swap the root(maximum value) of the heap with the''
        ''last element of the heap)''</span>
       swap(a[end], a[0])
       <span style="color: grey">''(decrement the size of the heap so that the previous''
        ''max value will stay in its proper place)''</span>
       end := end - 1
       <span style="color: grey">''(put the heap back in max-heap order)''</span>
       siftDown(a, 0, end)


 '''function''' heapify(a,count) '''is'''
    <span style="color: grey">''(start is assigned the index in ''a'' of the last parent node)''</span>
    start := (count - 2) / 2

    '''while''' start ≥ 0 '''do'''
       <span style="color: grey">''(sift down the node at index start to the proper place''
        ''such that all nodes below the start index are in heap''
        ''order)''</span>
       siftDown(a, start, count-1)
       start := start - 1
    <span style="color: grey">''(after sifting down the root all nodes/elements are in heap order)''</span>

 '''function''' siftDown(a, start, end) '''is'''
    <span style="color: grey">''(''end'' represents the limit of how far down the heap to sift)''</span>
    root := start

    '''while''' root * 2 + 1 ≤ end '''do'''       <span style="color: grey">''(While the root has at least one child)''</span>
       child := root * 2 + 1           <span style="color: grey">''(root*2+1 points to the left child)''</span>
       <span style="color: grey">''(If the child has a sibling and the child's value is less than its sibling's...)''</span>
       '''if''' child + 1 ≤ end '''and''' a[child] < a[child + 1] '''then'''
          child := child + 1           <span style="color: grey">''(... then point to the right child instead)''</span>
       '''if''' a[root] < a[child] '''then'''     <span style="color: grey">''(out of max-heap order)''</span>
          swap(a[root], a[child])
          root := child                <span style="color: grey">''(repeat to continue sifting down the child now)''</span>
       '''else'''
          '''return'''

<br>
Write a function to sort a collection of integers using heapsort.
<br><br>