动态分区算法Python代码

动态分区算法是一种常见的数据结构和算法，用于将一组数据划分成几个大小接近的子集，常用于数据库索引优化、任务调度等领域。Python中可以使用内置的`heapq`模块来实现类似二分查找树（堆）的动态分区方法。这里给出一个简单的例子，假设我们有一个列表并需要将其分割成两个部分，使得左侧部分元素之和尽可能接近右侧部分：

import heapq

def dynamic_partition(arr):
    # 使用堆来存储最大值
    max_heap = []
    # 初始化总和
    total = sum(arr)
    
    for num in arr:
        # 如果当前元素大于总和的一半，直接放到右边
        if len(max_heap) == 0 or -max_heap[0] <= num:
            heapq.heappush(max_heap, -num)
        else:
            # 否则，从堆中取出最大的负数添加到左边，并更新总和
            total -= heapq.heappop(max_heap)
        
    return total, [-x for x in max_heap]

# 示例
arr = [3, 5, -4, 8, 1, 9]
left_sum, right_sum = dynamic_partition(arr)
print(f"Left sum: {left_sum}, Right sum: {right_sum} ({sum(right_sum)})