Java Reference
In-Depth Information
9.3 Analysis of Heapsort
Is siftUp or siftDown better for creating a heap? Keep in mind that the most times any node will ever have to
move is log 2 n .
In siftDown , we process n /2 nodes, and at each step, we make two comparisons: one to find the bigger child and
one to compare the node value with the bigger child. In a simplistic analysis, in the worst case, we will need to make
2* n /2*log 2 n = n log 2 n comparisons. However, a more careful analysis will show that we need to make, at most, only 4 n
comparisons.
In siftUp , we process n -1 nodes. At each step, we make one comparison: the node with its parent. In a simplistic
analysis, in the worst case, we make ( n -1)log 2 n comparisons. However, it is possible that all the leaves may have to
travel all the way to the top of the tree. In this case, we have n /2 nodes having to travel a distance of log 2 n , giving
a total of ( n /2)log 2 n comparisons. And that's only for the leaves. In the end, a more careful analysis still gives us
approximately n log 2 n comparisons for siftUp .
The difference in performance is hinged on the following: in siftDown , there is no work to do for half the nodes
(the leaves); siftUp has the most work to do for these nodes.
Whichever method we use for creating the initial heap, heapsort will sort an array of size n making at most
2 n log 2 n comparisons and n log 2 n assignments. This is very fast. In addition, heapsort is stable in the sense that its
performance is always at worst 2 n log 2 n , regardless of the order of the items in the given array.
To give an idea of how fast heapsort (and all sorting methods that are of order O( n log 2 n ), such as quicksort and
mergesort) is, let's compare it with selection sort, which makes roughly ½ n 2 comparisons to sort n items (Table 9-1 ).
Table 9-1. Comparison of Heapsort with Selection Sort
n
selection(comp)
heap(comp)
select(sec)
heap(sec)
100
5,000
1,329
0.005
0.001
1,000
500,000
19,932
0.5
0.020
10,000
50,000,000
265,754
50
0.266
100,000
5,000,000,000
3,321,928
5000
3.322
1,000,000
500,000,000,000
39,863,137
500000
39.863
The second and third columns show the number of comparisons that each method makes. The last two columns
show the running time of each method (in seconds) assuming that the computer can process 1 million comparisons
per second. For example, to sort 1 million items, selection sort will take 500,000 seconds (almost 6 days!), whereas
heapsort will do it in less than 40 seconds.
9.4 Heaps and Priority Queues
A priority queue is one in which each item is assigned some “priority” and its position in the queue is based on this
priority. The item with top priority is placed at the head of the queue. The following are some typical operations that
may be performed on a priority queue:
Remove (serve) the item with the highest priority
Add an item with a given priority
Remove (delete without serving) an item from the queue
Change the priority of an item, adjusting its position based on its new priority
 
 
Search WWH ::




Custom Search