Java Reference
In-Depth Information
figure 21.38
Example of run
construction
Three Elements in Heap Array
Next
Item Read
array[1]
array[2]
array[3]
Output
11
94
81
11
96
81
94
96
81
12
Run 1
94
96
12
94
35
96
35
12
96
17
17
35
12
End of Run
Rebuild
12
35
17
12
99
17
35
99
17
28
28
99
35
28
58
Run 2
35
99
58
35
41
41
99
58
41
75
58
99
75
58
15
75
99
15
75
End of Tape
99
15
99
15
End of Run
Rebuild
Run 3
15
15
which case replacement selection produces only a few abnormally long runs.
This kind of input is common for external sorts and makes replacement selec-
tion extremely valuable.
In this chapter we showed an elegant implementation of the priority queue.
The binary heap uses only an array, yet it supports the basic operations in log-
arithmic worst-case time. The heap leads to a popular sorting algorithm, heap-
sort. In Exercises 21.26 and 21.27 you are asked to compare the performance
of heapsort with that of quicksort. Generally speaking, heapsort is slower than
quicksort but it is certainly easier to implement. Finally, we showed that prior-
ity queues are important data structures for external sorting.
This completes implementation of the fundamental and classic data struc-
tures. In Part Five we examine more sophisticated data structures, beginning
with the splay tree, a binary search tree that has some remarkable properties.
Search WWH ::
Custom Search