priority queues (heapssuppose we want to add the decreaseallkeysoperation to the heap repertoire the result of this operation is that all keys in the heap have their value decreased by an amount for the heap implementation of your choiceexplain the necessary modifications so that all other operations retain their running times and decreaseallkeys runs in ( which of the two selection algorithms has the better time boundthe standard copy constructor and makeempty for leftist heaps can fail because of too many recursive calls although this was true for binary search treesit is more problematic for leftist heapsbecause leftist heap can be very deepeven while it has good worst-case performance for basic operations thus the copy constructor and makeempty need to be reimplemented to avoid deep recursion in leftist heaps do this as followsa reorder the recursive routines so that the recursive call to ->left follows the recursive call to ->right rewrite the routines so that the last statement is recursive call on the left subtree eliminate the tail recursion these functions are still recursive give precise bound on the depth of the remaining recursion explain how to rewrite the copy constructor and makeempty for skew heaps references the binary heap was first described in [ the linear-time algorithm for its construction is from [ the first description of -heaps was in [ recent results suggest that -heaps may improve binary heaps in some circumstances [ leftist heaps were invented by crane [ and described in knuth [ skew heaps were developed by sleator and tarjan [ binomial queues were invented by vuillemin [ ]brown provided detailed analysis and empirical study showing that they perform well in practice [ ]if carefully implemented exercise ( -cis taken from [ exercise (cis from [ method for constructing binary heaps that uses about comparisons on average is described in [ lazy deletion in leftist heaps (exercise is from [ solution to exercise can be found in [ min-max heaps (exercise were originally described in [ more efficient implementation of the operations is given in [ and [ alternative representations for double-ended priority queues are the deap and diamond deque details can be found in [ ][ ]and [ solutions to (eare given in [ and [ theoretically interesting priority queue representation is the fibonacci heap [ ]which we will describe in the fibonacci heap allows all operations to be performed in ( amortized timeexcept for deletionswhich are (log nrelaxed heaps [ achieve identical bounds in the worst case (with the exception of mergethe procedure of [ achieves optimal worst-case bounds for all operations another interesting implementation is the pairing heap [ ]which is described in finallypriority queues that work when the data consist of small integers are described in [ and [