|
Heap Sort
This chapter helps you to understand:
- Basic Idea
- Java Implementation
- Performance
- Improvements
Basic Idea
The basic idea of Heap Sort is to:
1. Organize the entire collection of data elements as a binary tree stored
in an array indexed from 1 to N, where for any node at index i, its two children,
if exist, will be stored at index of 2*i, and 2*i+1.
2. Divide the binary tree into two parts, the top part in which data elements are in
their original order, and the bottom part in which data elements are in heap order,
where each node is in higher order than its children, if any.
3. Start the bottom part with the second half of the array, which contains only leaf
nodes. Of course, it is in heap order, because leaf nodes have no child.
4. Move the last node from the top part to the bottom part, compare its order
with its children,
and swap its location with its highest order child, if its order is lower
than any child. Repeat the comparison and swapping to ensure the bottom part is
in heap order again with this new node added.
5. Repeat step 4 until the top part is empty. At this time, the bottom part becomes
complete heap tree.
6. Now divided the array into two sections, the left section which contains
a complete heap tree, and the right section which contains sorted data elements.
7. Swap the root node with the last node of the heap tree in the left section, and
move it to the right section. Since the left section with the new root node
may not be a heap tree any more, we need to repeat step 4 and 5 to ensure
the left section is in heap order again.
8. Repeat step 7 until the left section is empty.
Java Implementation
Here is my Java implementation of Heap Sort algorithm:
/**
* HyArrays.java
* This class contains sorting methods similar to java.util.Arrays.
* All sorting methods should have a signiture of
* %Sort(Object[] a, int fromIndex, int toIndex)
* where "fromIndex" is inclusive, and "toIndex" is exclusive.
* Copyright (c) 1999 by Dr. Herong Yang
*/
public class HyArrays {
public static void heapSort(Object[] a, int fromIndex,
int toIndex) {
Object d;
int n = toIndex - fromIndex;
for (int i=n/2; i>=1; i--) {
downHeap(a,i,n,fromIndex);
}
for (int i=n; i>1; i--) {
d = a[fromIndex];
a[fromIndex] = a[fromIndex+i-1];
a[fromIndex+i-1] = d;
downHeap(a,1,i-1,fromIndex);
}
}
private static void downHeap(Object[] a, int i, int n,
int fromIndex) {
Comparable d = (Comparable)a[fromIndex+i-1];
int child;
while (i<=n/2) {
child = 2*i;
if (child<n && ((Comparable)a[fromIndex+child-1]).compareTo(
a[fromIndex+child])<0) {
child++;
}
if (d.compareTo(a[fromIndex+child-1])>=0) break;
a[fromIndex+i-1] = a[fromIndex+child-1];
i = child;
}
a[fromIndex+i-1] = d;
}
}
Note that:
- Data elements are stored in the input array between "fromIndex" and "toIndex",
and it is easier to manager a heap array with index from "1" to "n", so I have to
do some index conversions like "fromIndex+i-1".
Performance
Now let's see how it performs. I tried this implementation with my SortTest.java
under JDK 1.3.1.
Here are the results:
Array size: 10000
Average sorting time: 29 milliseconds
Number of tests: 1000
Performance: 2.9 O(N) nonaseconds
Performance: 0.21824674685638637 O(N*Log2(N)) nonaseconds
Performance: 2.9E-4 O(N*N) nonaseconds
Array size: 20000
Average sorting time: 76 milliseconds
Number of tests: 1000
Performance: 3.8 O(N) nonaseconds
Performance: 0.2659628006957283 O(N*Log2(N)) nonaseconds
Performance: 1.9E-4 O(N*N) nonaseconds
Array size: 30000
Average sorting time: 134 milliseconds
Number of tests: 1000
Performance: 4.466666666666667 O(N) nonaseconds
Performance: 0.30032705633819357 O(N*Log2(N)) nonaseconds
Performance: 1.488888888888889E-4 O(N*N) nonaseconds
The performance of this implementation is somewhat between quicksort and merge sort.
Improvements
I don't see area we can improve this easily.
| 