Sorting is usually performed not on isolated data, but records. Each record contains a key, which is the value to be sorted, and the remainder that is called satellite data.
Sorting is arguably the most fundamental problem in the study of algorithms for the following reasons:
Heapsort algorithm sorts in place and its running time is O(nlogn). Hence, it combines the better attributes of insertion sort and merge sort algorithms. It also introduces an important algorithm design technique: the use of data structure to manage information during the execution of the algorithm. In this case, it is "heap".
The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree. An array A that represents a heap is an object with two attributes: length[A], which is the number of elements, and heap-size[A], the number of elements in the heap stored within the array A.
A = {10, 8, 6, 5, 7, 3, 2}
10
8 6
5 7 3 2
The root of the tree is A[1]. Children of a node i determined as follows:
Left(i)
return 2i
Right(i)
return 2i+1
The above is proven by induction: the root's left child is 2 = 2*1. Assume it is true for node n. The left child of a node (n+1) will follow the right child of node n: left(n+1) = 2*n + 1 + 1 = 2(n+1) ÿ
The parent of a node is 2i/2, or floor(2i+1/2), hence:
Parent(i)
return floor(i/2)
In a max-heap, for every node i other than the root:
A[Parent(i)] >= A[i]
For the heapsort algorithm, we use max-heaps. The height of the heap is defined to be the longest path from the root to a leaf, and it is Q(lgn) since it is a complete binary tree. We will see that the basic operations on heap run in time proportional to the height, which is O(lgn). We will consider the following basic procedures on the heap:
The Max-Heapify procedure takes an array A and its index i. It is assumed that left and right subtrees are already sorted. The procedure lets the value of A[i] "float down" in the max-heap so that the subtree rooted at index i becomes a max-heap.
Max-Heapify (A, i)
1 l =
Left(i)
2 r =
Right(i)
3 if l
<= heap-size[A] and A[l] > A[i]
4 largest = l
5 else
6 largest = i
7 if r
<= heap-size[A] and A[r] > A[largest]
8 largest = r
9 if
largest <> i
10 <exchange A[i] with A[largest]
11 Max-Heapify(A, largest)
It takes Q(1) to find A[largest], plus the time to run the procedure recursively on at most 2n/3 elements. It is easy to see that the worst case occurs when the last row of the tree is exactly half full.
Assume there n nodes and x levels in the tree that has half of the last row. This means:
n = 1 + 2 + ... + 2^(x-1) + 2^x/2
2^x – 1 + 2^x/2 = n
2^(x-1) = a => 2a + a = n+1 =>
2^(x-1) = (n+1)/3
Max subtree size = (half of all elements to level x-1) +
(elements at the last level) –
(1 root element) =
(2^x – 1)/2 + 2^x/2 – 1 = 2^(x-1) – ½ + 2^(x-1) – 1 =
n/3 + 1/3 + n/3 + 1/3 – 1.5 = 2n/3 + 2/3 – 1.5 ~ 2n/3
Therefore the running time of Max-Heapify is described by the following recurrence:
T(n) <= T(2n/3) + Q(1)
According to case 2 of the master theorem:
f(n) = Q( n^logba) => T(n) = Q( n^logba lgn)
Here b=3/2; a=1 => T(n) = Q( lgn)
Since T(n) is the worst-case scenario, we have a running time of the algorithm at O(lgn).
We can use the procedure Max-Heapify in a bottom-up manner to convert the whole array A[1..n] into a max-heap.
Note that, elements A[floor(n/2)+1..n] are leaves. The last element that is not a leaf is a parent of the last node, which is floor(n/2).
The procedure Build-Max-Heap goes through all non-leaf nodes and runs Max-Heapify on each of them.
Build-Max-Heap(A, n)
1 heap-size[A]
= n
2 for
i = floor(n/2) to 1
3 Max-Heapify(A,i)
Invariant:
Proof:
Running time:
Each call to Max-Heapify takes O(lgn) time and there are n such calls. Therefore the running time of Build-Max-Heap is O(nlgn).
To derive a tighter bound, we observe that the running time of Max-Heapify depends on the node's height. An n-element heap has height floor(lgn). There are at most ceil(n/2^(h+1)) nodes of any height h. Assume these nodes are at height x of the original tree. Then we have:
1+2+...+2^x+...+2^h = n
2^(x+h+1) = n+1
2^x = (n+1)/2^(h+1) = ceil(n/2^(h+1))
The time required by Max-Heapify when called on a node of height h is O(h). Hence:
Sh=0,floor(lgn)ceil(n/2^(h+1)) O(h) = O(nSh=0,floor(lgn)h/2^h)
A.8: Sk=0,¥k/x^k = x/(1-x)^2
Sh=0,¥h/2^h = ½ / (1-1/2)^2 = 2
Thus, the running time of Build-Max-Heap can be bounded
O(n Sh=0,floor(lgn)h/2^h) = O(nSh=0,¥h/2^h) = O(n)
The heapsort algorithm uses Build-Max-Heap on A[1..n]. Since the maximum element of the array is at A[1], it can be put into correct position A[n]. Now A[1..(n-1)] can be made max-heap again.
Heapsort (A,n)
1 Build-Max-Heap(A,n)
2 for
i = n to 2
3 <swap A[1] with A[i]>
4 heap-size[A] = heap-size[A]-1
5 Max-Heapify(A,1)
Step 1 takes O(n) time. Loop 2 is repeated (n-1) times with step 5 taking most time O(lgn). Hence the running time of heapsort is O(n) + O(nlgn) = O(nlgn).