HEAP SORT

Heapsort relies on creating a certain kind of data structure called a HEAP.  A heap is an array (or binary tree) which has the property that for every element at location K, it is greater or equal to the elements at 2K & 2K+1.   Or to state it in another way:  v[ |_i/2_| ] >= v[i] where 1<=i<=N

An array that has the heap property is called a "heap". You can visualize a heap as a binary tree if that is more helpful.  Thus, an array is a heap if every path down the tree is in descending order by key field. In particular, v[1] has the maximum value.

e.g. 23, 19, 15, 17, 11, 13, 8, 9, 3, 4, 7, 12 is a heap because if you draw it as a binary tree, all paths down the tree will be in descending order by key.

The heap structure works well in any situation where we need to know only which element is next to be processed.

Basically:

• We develop a simple way of determining "who's next" which at the same time organizes the remaining elements sufficiently, that when they come near the head of the processing line, we can still easily determine "who's next".

• This is the basis for the method commonly used for allocating com. resources, the priority Q.

• You can think of a heap or a priority Q as having the property that the next element to be processed is at the head of the line, and all other elements are more-or-less in their proper positions but not exactly so.

There are actually two kinds of Heaps (both based on relationships between K, 2K, 2K+1)

Top-heavy : v[k] >= v[2k] and v[2k+1]   aka Max Heap

Bottom-heavy : v[k] < v[2k] and v[2k+1]   aka Min Heap

In both, we know nothing about the relationship between elements at 2k and 2k+1.

Consider the array of integers { 38, 37, 4, 47, 50, 90, 95 }.We can create a heap from this array by beginning with entry in location 2 (i.e., 37) and comparing it against its parent. If it's greater than its parent, we will swap integers.

This is the siftup procedure. It uses an insertion sort like algorithm to drive the large elements up the paths of the tree.  The next picture shows various iterations of the array (pictured as a binary tree) as the main Heapsort algorithm calls Siftup in a loop ranging from slot 2 to slot 7.  Subscripts I and J point to the integers they identify according to the Siftup algorithm.  The numbers in red indicate the subscript argument passed to that call to Siftup.

Stored as an array, our Heap now looks like this:  { 95, 47, 90, 37, 38, 4, 50 }

This is obviously not sorted, but we do know that the largest element is now the 1st element in the array.

To sort the array:

Exchange 1st element with the last. Now the largest number is in its correct position in the array, and we can forget about it.

{50, 47, 90, 37, 38, 4, 95}

We will then let the new 1st element in the array SIFTDOWN to its proper location in the heap.

i.e., siftdown takes the new root of the tree (key 50) and drives it down the tree until we have the heap property again.

The next picture walks you through the Siftdown process, as the main Heapsort algorithm swaps new large keys with new "last" positions, and calls on Siftdown to "re-heapify" the array.

The siftdown process is logarithmic in nature because at each comparison in sifting down, we eliminate one of the two substructures, either that at location 2k or 2k+1.

Since we do this logarithmic process n times, the process of forming a heap & then sorting it is:

O(n) + n (log n)

i.e. O(n log n) procedure

Both siftup and siftdown take time proportional to log N because both perform a fixed amount of work at each level of the heap.

A different version of HEAPSORT -- uses 1 extra procedure instead of two.

HEAPSORT(v,n)
i = (n/2)
Do While (i >= 1)
    RESTORE (i,n)
    i = i - 1
Enddo
i=n
Do While (i >= 1)
    Swap v[i] and v[1]
    RESTORE (1, i-1)
    i = i - 1
Enddo

RESTORE(F,L)
j = F
Do While ( 2*j <= L)
    If (2*j < L) & (v[2j] < v[2j+1])
        m = 2j+1
    else
        m = 2j
    endif
    If v[m] > v[j]
        Swap v[j] & v[m]
        j=m
    else
        j=L
    endif
Enddo