## Saturday, February 07, 2009

### heapsort

In heapsort,
- First put the elements of the array in a heap property (max-heap has the greater elements as parents) so that the first element is the max.
- The first element (root of heap) is swapped with the last element of the array (last leaf node of the heap) and the array is again put in heap property by sifting up or sifting down.

Sift-Down version: The sift-down version sifts the root or start down the heap.

The sift-down version takes O(logn) time.
```heapsort-siftdown(a):
maxheapify-siftdown(a)
end = a.length-1
while end > 0:
swap(a, 0, end)
end--
siftdown(a, 0, end)

maxheapify-siftdown(a):
start = a.length/2 -1 // last parent
while start >= 0:
siftdown(a, start, a.length-1)
start--

siftdown(a, start, end):
left = start*2 +1
right = left +1
max = start
if left <= end && a[left] > a[max]:
max = left
if right <= end && a[right] > a[max]:
max = right
if max != start:
swap(a, start, max)
siftdown(a, max, end)
```

Sift-Up version: The sift-up version builds the heap top-down as if starting with an empty heap and inserting new nodes. The child or end is sifted up to the root.

The sift-up version takes O(logn) time.
```heapsort-siftup(a):
maxheapify-siftup(a, a.length-1)
end = a.length-1
while end > 0:
swap(a, 0, end)
end--
maxheapify-siftup(a, end)

maxheapify-siftup(a, end):
child = 1
while child <= end:
siftup(a, child)
child++

siftup(a, end):
child = end
while child > 0:
parent = (child-1) /2
if a[parent] > a[child]:
break
swap(a, parent, child)
child = parent
```

The heap-sort with either version has O(nlogn) time efficiency.