 advanced data structures and implementation determine the time for partial match query for values of corresponding to and for perfectly balanced - treederive the worst-case running time of range query that is quoted in the text (see the - heap is data structure that allows each item to have two individual keys deletemin can be performed with respect to either of these keys the - heap is complete binary tree with the following order propertyfor any node at even depththe item stored at has the smallest key # in its subtreewhile for any node at odd depththe item stored at has the smallest key # in its subtree draw possible - heap for the items ( , )( , )( , )( , )( , how do we find the item with minimum key # how do we find the item with minimum key # give an algorithm to insert new item into the - heap give an algorithm to perform deletemin with respect to either key give an algorithm to perform buildheap in linear time generalize the preceding exercise to obtain - heapin which each item can have individual keys you should be able to obtain the following boundsinsert in (log )deletemin in ( log )and buildheap in (knshow that the - heap can be used to implement double-ended priority queue abstractlygeneralize the - heap so that only levels that branch on key # have two children (all others have onea do we need pointersb clearlythe basic algorithms still workwhat are the new time boundsuse - tree to implement deletemin what would you expect the average running time to be for random treeuse - heap to implement double-ended queue that also supports deletemin implement the pairing heap with nullnode sentinel show that the amortized cost of each operation is (log nfor the pairing heap algorithm in the text an alternative method for combinesiblings is to place all of the siblings on queueand repeatedly dequeue and merge the first two items on the queueplacing the result at the end of the queue implement this variation show that using stack instead of queue in the previous exercise is bad by giving sequence that leads to (ncost per operation this is the left-to-right single-pass merge without decreasekeywe can remove parent links how competitive is the result with the skew heapassume that each of the following is represented as tree with child and parent pointers explain how to implement decreasekey operation binary heap splay tree