Ленивая вставка / удаление

У меня есть назначение для редактирования очереди приоритетов и реализации (среди прочего) функции вставки. Несмотря на то, что моя книга упоминает «ленивое удаление» и другие ленивые действия, в ней никогда не указывается, что на самом деле означает «ленивый».

Короче:
В чем разница между функциями вставки / удаления и функциями вставки / удаления LAZY?

1

Решение

«Ленивое удаление» обычно означает, что вы помечаете что-то удаленное, а не удаляете его напрямую, и изменяете другие операции, чтобы сделать вид, что отмеченные элементы отсутствуют.

Например, в случае очереди с приоритетами вы можете перепрыгнуть через удаленные элементы в процедуре удаления очереди вместо того, чтобы активно удалять их из середины, что сложнее.

Точно так же «ленивая вставка» может добавить элементы во входную очередь, которая является операцией постоянного времени. Обычно вставка в приоритетную очередь занимает O (log n) времени. Входная очередь будет сброшена в приоритетную очередь при попытке удаления из очереди. Это приведет к разгрузке стоимости операции вставки до операции удаления из очереди.

По сути, «ленивый» означает не выполнять операцию, пока не потребуются ее результаты.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]