python - 为调度程序使用堆

Question

关于 Python 官方文档 here , 以下是关于堆的内容:

A nice feature of this sort is that you can efficiently insert new items while the sort is going on, provided that the inserted items are not “better” than the last 0’th element you extracted. This is especially useful in simulation contexts, where the tree holds all incoming events, and the “win” condition means the smallest scheduled time. When an event schedules other events for execution, they are scheduled into the future, so they can easily go into the heap

我只能想到下面的简单算法来实现一个使用堆的调度器:

# Priority queue using heap
pq = []
# The first element in the tuple represents the time at which the task should run.
task1 = (1, Task(...))
task2 = (2, Task(...))
add_task(pq, task1)
add_task(pq, task2)
# Add a few more root-level tasks
while pq:
    next_task = heapq.heappop()
    next_task.perform()
    for child_task in next_task.get_child_tasks():
        # Add new child tasks if available
        heapq.heappush(pq, child_task)

在这种情况下，排序甚至在哪里出现？
即使 future 的子任务有一个“过去”的时间，这个算法仍然可以正常工作。
那么，为什么作者警告说子事件只会在未来安排？
这是什么意思:

you can efficiently insert new items while the sort is going on, provided that the inserted items are not “better” than the last 0’th element you extracted.

Answer 1

堆被用作优先级队列的数据结构，事实上，最小堆的基本原理是最低优先级在顶部(或者在最大堆中，最高优先级在顶部)。因此，您始终可以提取最低或最高元素而无需搜索。

你总是可以在排序过程中插入新元素，试试看 heapSort 是如何工作的。每次你需要构建你的堆然后提取最大值并将它放在数组的末尾，在你将 heap.length 递减 1 之后。如果您已经对一些数字进行了排序:[..., 13, 15, 16] 并且您插入了一个比提取的最后一个元素(13 = 第 0 个元素)更高的新数字将得到错误的解决方案，因为您将提取新数字但不会将其放在正确的位置:[1, 2, 5, 7, 14, 13, 15, 16]。它将放置在 13 之前，因为它交换了 heap.length 位置上的元素。这显然是错误的，因此您只能插入小于第 0 个元素的元素。