Python如何向队列空缺中间位置插入元素而非末尾追加

结论 #

Python 没有原生内置的对应数据结构可以直接满足自动填充空缺索引的需求，你可以通过字典+最小堆的组合方案高效实现，增删操作的时间复杂度均为O(log n)，完全适配高频增删的使用场景。

实现思路 #

维护三个核心变量即可完成需求：

• 主存储字典：和你当前使用的嵌套字典结构一致，负责存储实际的业务数据
• 空缺索引最小堆：专门存储已经被删除的索引值，依托最小堆的特性可以每次快速获取到最小的空缺索引
• 最大索引计数器：记录无空缺索引时，下一个新增元素要分配的最大索引值

操作逻辑如下：

• 新增元素：优先检查最小堆是否存在空缺索引，存在则弹出堆顶最小索引作为新元素的键；不存在则使用最大索引计数器的值作为键，计数器同时自增1
• 删除元素：确认待删除索引存在后，将该索引推入最小堆，再执行字典的pop操作删除对应键值对

完整实现代码 #

import heapq

class AutoFillDict:
    def __init__(self, initial_data=None):
        self.data = {}
        self.free_ids = []
        self.next_max_id = 0
        # 导入初始数据
        if initial_data:
            for k, v in initial_data.items():
                if not isinstance(k, int) or k < 0:
                    raise ValueError("初始键必须为非负整数")
                self.data[k] = v
                if k >= self.next_max_id:
                    self.next_max_id = k + 1

    def add(self, value):
        # 优先取空缺索引
        if self.free_ids:
            new_id = heapq.heappop(self.free_ids)
        else:
            new_id = self.next_max_id
            self.next_max_id += 1
        self.data[new_id] = value
        return new_id

    def delete(self, item_id):
        if item_id not in self.data:
            raise KeyError(f"索引 {item_id} 不存在")
        heapq.heappush(self.free_ids, item_id)
        return self.data.pop(item_id)

    def __getitem__(self, item_id):
        return self.data[item_id]

    def __repr__(self):
        return repr(self.data)

# 测试用例
if __name__ == "__main__":
    initial_dict = {
        0: {"width": 10, "height": 5},
        1: {"width": 20, "height": 5},
        2: {"width": 10, "height": 15}
    }
    afd = AutoFillDict(initial_dict)
    print("初始状态：", afd)
    # 删除索引1
    afd.delete(1)
    print("删除索引1后：", afd)
    # 新增元素，优先填充空缺的1号索引
    new_id1 = afd.add({"width": 30, "height": 8})
    print(f"新增元素分配索引：{new_id1}，当前数据：{afd}")
    # 再新增元素，无空缺则分配3号索引
    new_id2 = afd.add({"width": 15, "height": 20})
    print(f"新增元素分配索引：{new_id2}，当前数据：{afd}")

运行效果 #

执行测试用例后输出如下：

初始状态： {0: {'width': 10, 'height': 5}, 1: {'width': 20, 'height': 5}, 2: {'width': 10, 'height': 15}}
删除索引1后： {0: {'width': 10, 'height': 5}, 2: {'width': 10, 'height': 15}}
新增元素分配索引：1，当前数据：{0: {'width': 10, 'height': 5}, 2: {'width': 10, 'height': 15}, 1: {'width': 30, 'height': 8}}
新增元素分配索引：3，当前数据：{0: {'width': 10, 'height': 5}, 2: {'width': 10, 'height': 15}, 1: {'width': 30, 'height': 8}, 3: {'width': 15, 'height': 20}}

内容的提问来源于stack exchange，提问作者polaupa