Использование кучи для планировщиков - PullRequest
Новая
       19

Использование кучи для планировщиков

2 голосов
/ 01 июня 2019

В официальных документах 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 элемент, который вы извлекли.

1 Ответ

0 голосов
/ 01 июня 2019

Кучи используются в качестве структуры данных для очереди с приоритетами, на самом деле фундаментальной для минимальной кучи является то, что у вас самый низкий приоритет сверху (или в максимальной куче - более высокий приоритет сверху). Поэтому вы всегда можете извлечь самый низкий или самый высокий элемент без поиска.

Вы всегда можете вставить новый элемент во время сортировки, попробуйте посмотреть, как работает heapSort. Каждый раз, когда вам нужно построить свою кучу, а затем извлечь максимальное значение и поместить его в конец массива, после уменьшения значения heap.length от 1. Если вы уже отсортировали некоторые числа: [..., 13, 15, 16] и вставили новое число, которое выше последнего извлеченного элемента (13 = 0-й элемент), вы получите неправильное решение, поскольку вы извлечете новое число, но вы не поставит его в нужное место: [1, 2, 5, 7, 14, 13, 15, 16]. Он будет помещен перед 13, потому что он поменяет элемент в позиции heap.length. Это, очевидно, неправильно, поэтому вы можете вставлять только те элементы, которые меньше 0-го элемента.

...