The Algorithm Design Manual (3rd) Exercise Solution 'E4-19'

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 4-19

Question

You wish to store a set of n numbers in either a max-heap or a sorted array. For each application below, state which data structure is better, or if it does not matter. Explain your answers.

• (a) Find the maximum element quickly.
• (b) Delete an element quickly.
• (c) Form the structure quickly.
• (d) Find the minimum element quickly.

Solution

Subproblem (a)

Conclusion

It does not matter.

Analisys

For max-heap, we get maximum by referencing the top of heap ($O(1)$), and for sorted array, which we consider is ascending sorted array, we get by referencing the last element ($O(1)$).

Subproblem (b)

Conclusion

Max-heap is better.

Analisys

Suppose we have a reference to an element to be deleted in advance.

For max-heap, it takes $O(\log{n})$ rearrangement time after the deletion, while for sorted array it takes $O(n)$ rearrangement time.

Subproblem (c)

Conclusion

Max-heap is better.

Analisys

Construction time comparison:

• Max-heap: $O(n)$
• Sorted array: $O(\log{n})$

Subproblem (d)

Conclusion

Sorted array is better.

Analisys

It takes $O(n)$ time for max-heap to find minimum because we must examine all leaf nodes. On the other hand, we get minimum element in sored array in $O(1)$ time by referencing the first element.