Какие операции вы бы использовали для реализации приоритетной очереди PQ с enqueue и dequeue?

Question

Предположим, что вы реализуете приоритетную очередь PQ, которая возвращает элемент max при операции удаления из очереди. Если мы используем максимальную кучу для реализации PQ, enqueue - это операция O (______), а dequeue - операция O (_____)

Может кто-нибудь ответить / объяснить, как у вас это получилось ... Я думаю, что log n для обоих, но не уверен?

Answer 1

Подумайте, как работает двоичная куча.

Когда вы вставляете элемент, вы добавляете его в качестве последнего узла кучи и затем поднимаете его на свое место. Поскольку куча, содержащая n элементов, имеет высоту log (n), и вам, возможно, придется просеять элемент до самого верха, наихудшим случаем будет O (log n).

При удалении элемент, вы заменяете заметку root последним узлом в куче, а затем откладываете его вниз. В худшем случае, вам придется просеять его до самого конца кучи: перемещение уровней log (n). Следовательно, O (log n).