There are 2 other terms used in heap sort are siftDown and siftUp.
SiftDown is the procedure to swap the node with its min-value/max-value of children nodes. When swapping is performed, check the subtrees (or sub-heap) of the corresponding child nodes recursively.
The procedure of SiftDown with a given index n:
Checking the node n key value with its min (children nodes 2*n and 2*n+1)
Min node = min (children nodes 2*n and 2*n+1) key values
If Min node key value < node n key value
Swap (node n, min node)
SiftDown(array, min node)
The worst time complexity of Heapify using SiftDown is O(nlog(n)), But the following analysis shows that it’s a constant time:
- Heapify takes O(1) for nodes that are one level above the leaves. In general O(l) for nodes that are l levels above the leaves.
- We have n/4 nodes with level 1, n/8 nodes level 2, … 1 node at log(n) level.
- Total amount of time = n/4 (c )+ n/8 (2c) + n/16(3 c) …+ 1 log(n)
- Set n/4 = 2**k
- Total amount of time = c * 2**k ( 1/2**0 + 2/2**1 + 3/2**2 + ….(k+1)/2**k) → this equation is bounded by constant.
- Total amount of time = ∑ i=0 to k ( i+1/2**i)
Heapsort:
This algorithm is written by J.W.J.Williams in 1964. This is the in-place algorithm where no extra array space is not required. This is a non-stable algorithm where the nodes with the same k value may change their positions.
This uses the concept of min/max heap.
Heapsort algorithm:
· Build Max/Min heap from an unordered array
· Find the Max/Min element array[0],
· Swap with the end of the array element
· Decrement the number of elements by removing the last element
· Rebuild the heap and repeat the above procedure till the number of elements is 1.
SiftUp is the procedure that can be assumed as starting with an empty heap and successively inserting elements. SiftUp call increases with the depth of the node on which call is made.
Heapsort algorithm with siftUp procedure:
procedure heapify(a,count) is
(end is assigned the index of the first (left) child of the root)
end := 1
while end < count
(sift up the node at index end to the proper place such that all nodes above
the end index are in heap order)
siftUp(a, 0, end)
end := end + 1
(after sifting up the last node all nodes are in heap order)
procedure siftUp(a, start, end) is
input: start represents the limit of how far up the heap to sift.
end is the node to sift up.
child := end
while child > start
parent := iParent(child)
if a[parent] < a[child] then (out of max-heap order)
swap(a[parent], a[child])
child := parent (repeat to continue sifting up the parent now)
else
return
The siftUp subroutine alone cannot fix the broken heap. The heap needs to be built every time after a swap by calling the heapify procedure since "siftUp" assumes that the element getting swapped ends up in its final place, as opposed to "siftDown" allows for continuous adjustments of items lower in the heap until the invariant is satisfied. The adjusted pseudocode for using siftUp approach is given below.
procedure heapsort(a, count) isinput: an unordered array a of length count(Build the heap in array a so that largest value is at the root)heapify(a, count)(The following loop maintains the invariants that a[0:end] is a heap and every element beyond end is greater than everything before it (so a[end:count] is in sorted order))end ← count - 1while end > 0 do(a[0] is the root and largest value. The swap moves it in front of the sorted elements.)swap(a[end], a[0])(rebuild the heap using siftUp after the swap ruins the heap property)heapify(a, end)(reduce the heap size by one)end ← end - 1
References:
- Internet
