Please Solve This Problem With C 1 (199.84 KiB) Viewed 24 times
Please Solve This Problem With C 2 (110.21 KiB) Viewed 24 times
Max Heap Heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either > (in a max heap) or < (in a min heap) the key of C. The node at the "top" of the heap (with no parents) is called the root node. In binary-tree based heap, it can be implemented via an array with property: if a node in the binary tree has index i, then its two children have index 2i, 2i+1 respectively. The following is an example of a Max-Heap: TIT [2]M 131-59 [41-48 151 19--11 {71-26 461 15 1 [8] [9] [10] (20) Index 1 2 3 4 5 6 7 8 9 10 Value 77 61 59 48 19 11 26 15 1 5 There are two main operations on heap: Insert a new key: append new key to the end of the array, and then adjust the heap Pop root node: replace the root by the last node in the array, and then adjust the heap Insert: Initially, 20 20 heap size is 5. We insert x in to X array[6], and continue swapping the node (x) with its (10 (14) 10 10 farther node if x> farther.key (adjust) 10 15 Pop: 20) Initially heap size is 5. We replace the root node by the last node (x=10) in the 14 array (pop). Then (10) continue swapping the new node (x=10) with the children node if x<child.key (adjust)
In this question, you need to implement the data structure of Max-Heap with functions insert() and pop(). Libraries such as <algorithm> <queue> already implements the heap (make_heap in <algorithm>, priority_queue in <queue>), therefore you are not allowed to use these libraries. Input The input contains multiple test cases. Each test case begins with one integer n (0 sns 100000), indicating the number of operations. The following n lines give the operations on the heap, each line follows the format: "ak": insert a new number k to the heap, 1 sk < 1000. pop (remove) the root node of the heap. "r": print the sum of all numbers in the heap. It will guarantee that the heap is not empty when encountered with pop operation. Output For each "r" operation, print the sum in a separate line. "p": Sample input 13 a 61 Sample output 184 4 a 1 5 a 77 a 19 a 26 a 15 a 59 a 5 a 48 a 11 p р r 8 a 5 a 4 р r a 2 a 3 p r In the first sample, after inserting the integers {61, 1, 77, 19, 26, 15, 59, 5, 48, 11}, we'll get the max-heap shown in the above picture. Then after two pop operations, 77 and 61 will be popped out and the sum of the remaining numbers is 184.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!