如何对包含HuffmanTree对象与元组的异构列表进行排序？

需求说明 #

需要处理一个混合了**(字符, 频率)元组和HuffmanTree对象**的列表，核心流程是：

• 每次从列表中弹出两个频率/权重最低的元素
• 用这两个元素生成一棵新的HuffmanTree
• 将新树重新加入列表并重新排序
• 重复上述步骤直到列表只剩一个元素（最终哈夫曼树）

现有初始元组排序代码如下：

sorted_freq = []
for element in freq_dict:
    element_in_tuple_form = (element, freq_dict[element])
    sorted_freq.append(element_in_tuple_form)
sorted_freq = sorted(sorted_freq, key=lambda x: x[1], reverse=False)

疑问：当列表中加入HuffmanTree对象后，能否实现按元组的频率值和树的weight属性统一排序？例如以下场景：

sort_me = [("a", 1), ("b", 3), HuffmanTree(2)] 
sort_me = sorted(...) 
print(sort_me) 
>>> [("a", 1), HuffmanTree(2), ("b", 3)]

解决方案 #

可以通过自定义sorted函数的key参数实现异构元素的统一排序，核心是判断元素类型并提取对应的排序依据：

1. 自定义排序Key函数 #

def get_weight(item):
    # 判断元素类型，返回对应的权重/频率值
    if isinstance(item, tuple):
        return item[1]
    elif isinstance(item, HuffmanTree):
        return item.weight
    else:
        raise ValueError("列表元素只能是元组或HuffmanTree对象")

2. 完整示例代码 #

先实现符合属性要求的HuffmanTree类：

class HuffmanTree:
    def __init__(self, weight, left=None, right=None, symbol=None):
        self.weight = weight
        self.left = left
        self.right = right
        self.symbol = symbol
    
    def __repr__(self):
        # 自定义打印格式，方便调试查看
        return f"HuffmanTree({self.weight})"

然后演示排序和哈夫曼树构建流程：

# 初始元组列表构建
freq_dict = {"a":1, "b":3}
sorted_freq = [(k, v) for k, v in freq_dict.items()]
sorted_freq = sorted(sorted_freq, key=get_weight)

# 加入一棵HuffmanTree对象
sorted_freq.append(HuffmanTree(2))

# 重新排序验证
sorted_freq = sorted(sorted_freq, key=get_weight)
print(sorted_freq)  # 输出: [('a', 1), HuffmanTree(2), ('b', 3)]

# 模拟哈夫曼树完整构建循环
while len(sorted_freq) > 1:
    # 弹出两个权重最低的元素
    item1 = sorted_freq.pop(0)
    item2 = sorted_freq.pop(0)
    
    # 计算新树权重并创建节点
    new_weight = get_weight(item1) + get_weight(item2)
    new_tree = HuffmanTree(new_weight, left=item1, right=item2)
    
    # 加入新树并重新排序
    sorted_freq.append(new_tree)
    sorted_freq = sorted(sorted_freq, key=get_weight)

# 最终生成的哈夫曼树
final_tree = sorted_freq[0]
print(f"最终哈夫曼树总权重: {final_tree.weight}")  # 输出: 最终哈夫曼树总权重: 6

说明 #

• get_weight函数是核心，它统一了元组和HuffmanTree对象的权重提取逻辑
• 每次加入新树后，调用sorted(sorted_freq, key=get_weight)即可完成异构列表的升序排序
• 弹出元素时直接取列表首个元素即可，因为排序后列表已按权重从小到大排列

内容的提问来源于stack exchange，提问作者Yusuf Gökçe