时间戳

首页 > 解决方案 > 为调度程序使用堆

python - 为调度程序使用堆

问题描述

在此处的 Python 官方文档中，提到了以下关于堆的内容：

这种排序的一个很好的特性是您可以在排序进行时有效地插入新项目，前提是插入的项目不比您提取的最后一个第 0 个元素“更好”。这在模拟环境中特别有用，其中树包含所有传入事件，“获胜”条件意味着最小的预定时间。当一个事件调度其他事件执行时，它们被调度到未来，因此它们可以很容易地进入堆

我只能想到以下简单的算法来实现使用堆的调度程序：

# 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)

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

您可以在排序进行时有效地插入新项目，前提是插入的项目不比您提取的最后一个第 0 个元素“更好”。

标签： pythonalgorithmscheduled-tasksheapscheduler

解决方案

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

您可以随时在排序期间插入新元素，尝试查看 heapSort 的工作原理。每次你需要建立你的堆，然后提取最大值并将其放在数组的末尾，在你减少 heap.length 1之后。如果你已经对一些数字进行了排序：[..., 13, 15, 16]并且你插入一个更高的新数字提取的最后一个元素（13 = 0'th 元素）你会得到一个错误的解决方案，因为你会提取新的数字，但你不会把它放在正确的位置：[1, 2, 5, 7, 14, 13, 15, 16]. 它将被放置在 13 之前，因为它交换了 heap.length 位置上的元素。这显然是错误的，因此您只能插入少于第 0 个元素的元素。

推荐阅读