CLRS 9.1 Minimum and maximum | Rip's Infernal Majesty
9.1-1
Show that the second smallest of n elements can be found with n + ⌈lg n⌉ – 2 comparisons in the worst case. (Hint: Also find the smallest element.)
We can borrow idea from heap sort. Build a min-heap of these n elements, which always takes less than n comparisons. Then we extract the root from heap which is the smallest element we want. After that we call HEAPIFY once, which takes ⌈lg n – 1⌉ comparisons at worst. Now we can extract the new root which is the second smallest element. In total this takes n + ⌈lg n⌉ – 2 comparisons at most.
9.1-2: ⋆
Show that ⌈3n/2⌉ – 2 comparisons are necessary in the worst case to find both the maximum and minimum of n numbers. (Hint: Consider how many numbers are potentially either the maximum or minimum, and investigate how a comparison affects these counts.)
Compare numbers in pairs. The smaller of subsequent pair is compared to the current min, and the larger to the current max. Thus there are 3 comparisons for each pair, except the first pair taking only one comparison. It results in total ⌈3n/2-2⌉ comparisons.
Read full article from CLRS 9.1 Minimum and maximum | Rip's Infernal Majesty
No comments:
Post a Comment