12.20 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 is a complete binary tree with the following order property: For any node X at even depth, the item stored at X has the smallest key #1 in its subtree, while for any node 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. - | |
| View Solution | |
| << Back | Next >> |