This code reads an integer `t` from input and then iterates `t` times. In each iteration, it reads an integer `n` and a list of `n` integers from input. It then transforms the list of integers into a min heap using the `heapq.heapify()` method.
The code then initializes a variable `wpl` (which likely stands for weighted path length) to 0. It enters a loop that continues as long as there are at least 2 elements in the heap. In each iteration of the loop, it extracts the two smallest elements (`a` and `b`) from the heap using `heapq.heappop()`, adds their sum to `wpl`, and then pushes the sum back into the heap using `heapq.heappush()`.
At each iteration, the sum of the two smallest elements is added to the weighted path length. After the loop finishes, the final weighted path length is printed.
Overall, this code seems to be implementing Huffman Encoding algorithm to find the optimal prefix code for the given list of numbers. The weighted path length calculated here represents the total cost of constructing a Huffman tree for the given list of numbers.
1 import heapq 2 3 t = int(input()) 4 for i in range(t): 5 n = int(input()) 6 nums = list(map(int, input().split())) 7 heapq.heapify(nums) 8 9 wpl = 0 10 while len(nums) > 1: 11 a = heapq.heappop(nums) 12 b = heapq.heappop(nums) 13 wpl += a+b 14 heapq.heappush(nums, a + b) 15 print(wpl)
1 class TreeNode: 2 def __init__(self, val): 3 self.val = val 4 self.left = None 5 self.right = None 6 7 def insert(root, val): 8 if root is None: 9 return TreeNode(val) 10 if val < root.val: 11 root.left = insert(root.left, val) 12 elif val == root.val: 13 return root 14 else: 15 root.right = insert(root.right, val) 16 return root 17 18 def preorder(root): 19 if root is None: 20 return [] 21 return [root.val] + preorder(root.left) + preorder(root.right) 22 23 def main(): 24 import sys 25 input = sys.stdin.read().strip() 26 if not input: 27 print() 28 return 29 nums = list(map(int, input.split())) 30 root = None 31 for num in nums: 32 root = insert(root, num) 33 result = preorder(root) 34 print(' '.join(map(str, result))) 35 36 if __name__ == "__main__": 37 main()
1 from collections import defaultdict 2 3 def find_public_ancestor(n, nums): 4 parents = defaultdict(int) 5 for num in nums: 6 parents[num] += 1 7 while num != 1: 8 num //= 2 9 parents[num] += 1 10 candidate = [] 11 for parent in parents: 12 if parents[parent] == n: 13 candidate.append(parent) 14 candidate.sort() 15 print(candidate[-1]) 16 17 18 t = int(input()) 19 for _ in range(t): 20 n = int(input()) 21 nums = list(map(int, input().split())) 22 find_public_ancestor(n, nums)