Вывести значения в двоичную кучу в отсортированном порядке, используя поиск в ширину?

Question

Я сейчас читаю эту статью и на пятой странице обсуждаются свойства двоичных куч, которые она считает общеизвестными.Тем не менее, одно из замечаний, которые они делают, - это то, чего я раньше не видел и не могу понять.Авторы утверждают, что если вы получаете сбалансированную двоичную кучу, вы можете перечислить элементы этой кучи в отсортированном порядке за O (log n) времени на элемент, используя стандартный поиск в ширину.Вот их первоначальная формулировка:

В сбалансированной куче любой новый элемент может быть вставлен в логарифмическом времени.Мы можем перечислить элементы кучи по порядку по весу, используя логарифмическое время для генерации каждого элемента, просто используя поиск в ширину.

Я не уверен, что авторы подразумевают под этим.Первое, что приходит на ум, когда они говорят «поиск в ширину», это поиск в ширину элементов дерева, начинающихся с корня, но это не гарантирует перечисления элементов в отсортированном порядке, а также не требует логарифмического времени.за элемент.Например, запуск BFS в этой минимальной куче приводит к тому, что элементы не в порядке, независимо от того, как вы разорвете связи:

             1
            / \
          10   100
         /  \
        11  12

Это всегда перечисляет 100 перед 11 или 12, что явно неверно.

Я что-то упустил?Существует ли простой поиск в ширину, который вы можете выполнить в куче, чтобы получить элементы в отсортированном порядке, используя логарифмическое время каждый?Ясно, что вы можете сделать это путем деструктивного изменения кучи, удаляя каждый раз минимальный элемент, но авторы, похоже, намереваются сделать это неразрушающим образом.

Answer 1

Вы можете получить элементы в отсортированном порядке, обходя кучу с приоритетной очередью (которая требует другой кучи!).Я предполагаю, что это то, что он называет «поиском в ширину».

Я думаю, вы должны быть в состоянии понять это (учитывая вашу репутацию в алгоритмах), но в основном ключом очереди приоритета является весузла.Вы помещаете корень кучи в очередь с приоритетами.Тогда:

while pq isn't empty
    pop off pq
    append to output list (the sorted elements)
    push children (if any) onto pq

Я не совсем уверен (вообще), если это то, о чем он имел в виду, но это смутно соответствовало описанию, и там не было большой активности, поэтому я подумал, что мог бы такжеположить его там.

Answer 2

Если вы знаете, что все элементы ниже 100 слева, вы можете пойти налево, но в любом случае, даже если вы достигнете 100, вы увидите, что слева нет элементов, поэтому вы выходите.В любом случае вы дважды выходите из узла (или любого другого узла) в худшем случае, прежде чем поймете, что нет элемента, который вы ищете.Чем мужчины, которые вы заходите в это дерево не более 2 * log (N) раз.Это упрощено до логарифмической (N) сложности.

Дело в том, что даже если вы «облажаетесь» и переходите к «неправильному» узлу, вы переходите на этот узел в худшем случае один раз.

РЕДАКТИРОВАТЬ
Вот как работает heapsort.Вы можете себе представить, что вам нужно восстанавливать кучу, используя N (log n) сложности каждый раз, когда вы берете верхний элемент.