The 2-d heap is a data structure that allows each item to have two individual

Chapter 12, Problem 12.20

(choose chapter or problem)

The 2-d heap is a data structure that allows each item to have two individual keys.deleteMin can be performed with respect to either of these keys. The 2-d heap isa complete binary tree with the following order property: For any node X at evendepth, the item stored at X has the smallest key #1 in its subtree, while for anynode X at odd depth, the item stored at X has the smallest key #2 in its subtree.a. Draw a possible 2-d heap for the items (1, 10), (2, 9), (3, 8), (4, 7), (5, 6).b. How do we find the item with minimum key #1?c. How do we find the item with minimum key #2?d. Give an algorithm to insert a new item into the 2-d heap.e. Give an algorithm to perform deleteMin with respect to either key.f. Give an algorithm to perform buildHeap in linear time.