Problem $1($Least$-$k Elements Datastructure$)$

We saw how min$-$heaps can efficiently allow us to query the least element in a heap $($array$).$ We would like to modify minheaps

in this exercise to design a data structure to maintain the least $k$ elements for a given $k1$ with

$k=1$

being the minheap data$-$structure.

Our design is to hold two arrays:

$($a$)$ a sorted array A of $k$ elements that forms our least $k$ elements; and

$($b$)$ a minheap $H$ with the remaining $n-k$ elements.

Our data structure will itself be a pair of arrays $(A,H)$ with the following property:

H must be a minheap

A must be sorted of size $k.$

Every element of A must be smaller than every element of $H.$

The key operations to implement in this assignment include:

insert a new element into the data$-$structure

delete an existing element from the data$-$structure.

We will first ask you to design the data structure and them implement it$.$

$($A$)$ Design Insertion AlgorithmSuppose we wish to insert a new element with key $j$ into this data structure. Describe the pseudocode. Your pseudocode must

deal with two cases: when the inserted element $j$ would be one of the least $k$ elements i$.$e$,$ it belongs to the array $A$; or

when the inserted element belongs to the heap $H.$ How would you distinguish between the two cases?

You can assume that heap operations such as insert $,$ key$)$ and delete$(H,$ index$)$ are defined.

Assume that the heap is indexed as $H[1],$dots,$H[n-k]$ with $H[]$ being unused.

Assume $n>k,$ i$.$e$,$ there are already more than $k$ elements in the data structure.

What is the complexity of the insertion operation in the worst case in terms of $k,n.$

Unfortunately, we cannot grade your answer. We hope you will use this to design your datastructure on paper before

attempting to code it up

YOUR ANSWER HERE

$($B$)$ Design Deletion Algorithm

Suppose we wish to delete an index $j$ from the top$-$k array $A.$ Design an algorithm to perform this deletion. Assume that the

heap is not empty, in which case you can assume that the deletion fails.

You can assume that heap operations such as insert $,$ key$)$ and delete$(H,$ index$)$ are defined.

Assume that the heap is indexed as $H[1],$dots,$H[n-k]$ with $H[]$ being unused.

Assume $n>k,$ i$.$e$,$ there are already more than $k$ elements in the data structure.

What is the complexity of the insertion operation in the worst case in terms of $k,n.$

Unfortunately, we cannot grade your answer. We hope you will use this to design your datastructure on paper before

attempting to code it up

YOUR ANSWER HERE$($C$)$ Program your solution by completing the code below

Note that although your algorithm design above assume that your are inserting and deleting from cases where $nk,$ the data

structure implementation below must handle $nas$ well. $We$ have provided implementations for that portion $to$ help you

out.