题解 | 哈夫曼编码 -最小堆-优先队列

import sys

# for line in sys.stdin:
#     a = line.split()
#     print(int(a[0]) + int(a[1]))


"""
 哈夫曼编码
 https://blog.csdn.net/xyy1028/article/details/139965597
 
 哈夫曼编码的核心思想： 
 高频字符用短编码 ，低频符号用长编码，从而最小化总编码长度。
算法思路：
1.优先队列（最小堆）
将所有字符的频率存入最小堆，每次取出两个最小的频率合并
直到对重只剩下一个节点。
合并时，记录每次合并的权值之和，这些权值的累加为最小编码长度。
2. 计算最短编码长度
  每次合并两个最小频率a和b ，生成新的节点a+b ，并将a+b 重新
  放入堆中。
  总编码长度=所有非叶子节点的权值之和（每次合并的a+b 的累加）。
示例解析‌
‌输入‌：n = 3，a = [1, 2, 3]
‌步骤‌：
初始堆：[1, 2, 3]
合并 1 和 2 → 3（总长度 +3），堆变为 [3, 3]
合并 3 和 3 → 6（总长度 +6），堆变为 [6]
‌总长度‌ = 3 + 6 = 9（与示例一致）。

复杂度： 
时间复杂度：O(n log n ) 每次堆操作 o(log n)  ，共 n次。
空间复杂度： O(n) 堆存储
关键点‌
‌堆优化‌：直接使用 heapq 模块，避免手动实现堆。
‌贪心策略‌：每次合并最小的两个节点，确保总编码长度最小化。
‌边界情况‌：当 n = 1 时，无需合并，总长度为 0（但题目保证 a_i ≥ 1，故 n ≥ 1 时至少有一个字符）。
"""
import heapq
def solve():
    n =int(input())
    a= list(map(int,input().split()))
    total=0
    heapq.heapify(a)
    while len(a)>1:
        x= heapq.heappop(a)
        y=heapq.heappop(a)
        cost=x+y
        total+=cost
        heapq.heappush(a,cost)
    print(total)

solve()