Question

Heapsort

Show that, with array representation for storing an n-element heap, the leaves are the nodes indexed by [n/2]+1, [n/2]+2….n. (2 points)

Show that each child of the root of an n-node heap is the root of a subtree containing at most 2n/3 nodes. What is the smallest constants α such that each subtree has at most αn nodes? (2 points)

The operation MAX-HEAP-DELETE (A, x) deletes the object x from the max-heap A. Give an implementation of MAX-HEAP-DELETE for an n-element. Also show the run-time analysis? (2 points)

Quicksort

When RANDOMIZATION_QUICKSORT runs, how many calls are made to the random-number generator RANDOM in the worst case? How about the best case? Give the answers in terms of ϴ notation? (2 points)

What value of q does PARTITION return when all elements in the subarray A [p: r] have the same value? Modify the partition so that q= [(p+r)/2] when all elements in the subarray A [p: r] have the same value? (2 points)

Answer 1

Leaves of an n-element heap's binary tree are indexed from [n/2]+1 to n, and each child of the root can be the root of a subtree with at most 2n/3 nodes. The MAX-HEAP-DELETE operation's runtime is O(log n), while RANDOMIZATION_QUICKSORT's random-number generator calls are Θ(n) in the worst case and Θ(log n) in the best case. Partition's q value can be set to [(p+r)/2] when all elements are the same.

Step-by-step explanation:

Heapsort and Quicksort Analysis

Heapsort is a popular sorting algorithm that utilizes a binary heap data structure. In array representation for an n-element heap, the leaves of the heap are indexed by [n/2]+1 to n. This is because in a complete binary heap, the level before the last contains all nodes that have at least one child (i.e., non-leaf nodes), and this level is filled from left to right up to index n/2. Therefore, the indices beyond n/2 are all leaves.

Each child of the root of an n-node heap represents the root of a subtree. If the heap is unbalanced, the most extreme situation occurs when one subtree has the minimum number of nodes while the root and the other subtree split the remaining nodes. In this case, the subtree has at most 2n/3 nodes because the binary heap is a complete tree and the number of nodes at each level at most doubles, which leads to the smallest constant α=2/3.

For the MAX-HEAP-DELETE operation, a potential implementation could follow these steps: find the node containing object x, replace its value with the value in the last node of the heap, reduce the heap's size by one, and finally re-heapify the heap to maintain the max-heap property. The runtime analysis of this operation is O(log n), due to the re-heapifying step, which is the most time-consuming part.

During RANDOMIZATION_QUICKSORT, the number of calls to the random-number generator depends on the number of recursive calls to the algorithm. In the worst case, if the partitioning is so unbalanced that it only reduces the problem size by one element each time, there will be n calls, leading to a worst-case call count expressed in Θ(n). In the best case, the partition is always balanced, leading to Θ(log n) calls due to the logarithmic height of the perfectly balanced recursion tree.

If all elements in the subarray A[p:r] are identical, the PARTITION function would return either p or r, depending on the implementation. To ensure that q is set to [(p+r)/2] under this condition, an additional check can be incorporated into the partition algorithm to test for equality of elements and adjust the pivot accordingly.