Мин-макс куча

Мин-макс куча
Мин-макс куча
Тип	двоичное дерево/куча
Изобретенный	1986
Операция
Временная сложность в обозначении большого О
Операция	Средний
Вставлять	О (логарифм n)
Удалить	О (логарифм n)
Пространственная сложность

В информатике минимальная -максимальная куча представляет собой полную двоичного дерева структуру данных , которая сочетает в себе полезность как минимальной, так и максимальной кучи , то есть обеспечивает постоянное время поиска и логарифмическое время удаления как минимума, так и максимума. элементы в нем. ^[2] Это делает кучу min-max очень полезной структурой данных для реализации двусторонней очереди с приоритетами . Подобно двоичным минимальным и максимальным кучам, минимальные и максимальные кучи поддерживают логарифмическую вставку и удаление и могут создаваться за линейное время. ^[3] Минимально-максимальные кучи часто неявно представляются в виде массива ; ^[4] поэтому ее называют неявной структурой данных .

Свойство кучи min-max таково: каждый узел на четном уровне дерева меньше всех своих потомков, а каждый узел на нечетном уровне дерева больше всех своих потомков . ^[4]

Структуру также можно обобщить для эффективной поддержки других операций со статистикой заказов, таких как find-median, delete-median, ^[2]find(k) (определить k-е наименьшее значение в структуре) и операцию delete(k) (удалить k-е наименьшее значение в структуре) для любого фиксированного значения (или набора значений) k . Эти последние две операции могут быть реализованы за постоянное и логарифмическое время соответственно. Понятие мин-максного упорядочения можно распространить на другие структуры, основанные на максимальном или мин-упорядочении, такие как левые деревья , создавая новый (и более мощный) класс структур данных. ^[4] Куча min-max также может быть полезна при реализации внешней быстрой сортировки. ^[5]

Описание

Куча min-max — это полное двоичное дерево, содержащее чередующиеся минимальные (или четные ) и максимальные (или нечетные ) уровни . Четные уровни — это, например, 0, 2, 4 и т. д., а нечетные уровни — соответственно 1, 3, 5 и т. д. В следующих пунктах мы предполагаем, что корневой элемент находится на первом уровне, т. е. 0.

Каждый узел в куче min-max имеет элемент данных (обычно называемый ключом ), значение которого используется для определения порядка узла в куче min-max.
Корневой . элемент — это самый маленький элемент в куче min-max
Один из двух элементов второго уровня, который является максимальным (или нечетным) уровнем, является наибольшим элементом в куче min-max.
Позволять $x$ $х$ быть любым узлом в куче min-max.
- Если $x$ находится на минимальном (или даже) уровне, то $x.key$ — минимальный ключ среди всех ключей в поддереве с корнем $x$ .
- Если $x$ находится на максимальном (или нечетном) уровне, то $x.key$ — максимальный ключ среди всех ключей в поддереве с корнем $x$ .
Узел на минимальном (максимальном) уровне называется минимальным (максимальным) узлом.

Макс -минутная куча определяется аналогично; в такой куче максимальное значение хранится в корне, а наименьшее значение хранится в одном из дочерних элементов корня. ^[4]

Операции

В следующих операциях мы предполагаем, что минимальная-максимальная куча представлена в виде массива. A[1..N]; $ith$ место в массиве будет соответствовать узлу, расположенному на уровне $\lfloor \log _{2}i\rfloor$ в куче.

Строить

Создание минимально-максимальной кучи достигается путем адаптации алгоритма построения кучи Флойда с линейным временем, который действует восходящим способом. ^[4] Флойда построения кучи Типичный алгоритм ^[6] происходит следующим образом:

function FLOYD-BUILD-HEAP(h):
    for each index i from  $\lfloor length(h)/2\rfloor$ down to 1 do:
        push-down(h, i)
    return h

В этой функции h — это исходный массив, элементы которого не могут быть упорядочены по свойству кучи min-max. push-down операция (которую иногда также называют heapify Далее объясняется ) с кучей min-max.

Нажмите вниз

The push-down алгоритм (или trickle-down как это называется в ^[4] ) выглядит следующим образом:

function PUSH-DOWN(h, i):
    if i is on a min level then:
        PUSH-DOWN-MIN(h, i)
    else:
        PUSH-DOWN-MAX(h, i)
    endif

Нажмите вниз мин.

function PUSH-DOWN-MIN(h, i):
    if i has children then:
        m := index of the smallest child or grandchild of i
        if m is a grandchild of i then:
            if h[m] < h[i] then:
                swap h[m] and h[i]
                if h[m] > h[parent(m)] then:
                    swap h[m] and h[parent(m)]
                endif
                PUSH-DOWN(h, m)
            endif
        else if h[m] < h[i] then:
            swap h[m] and h[i]
        endif 
    endif

Нажмите вниз Макс

Алгоритм push-down-max идентично оператору push-down-min, но все операторы сравнения поменяны местами.

function PUSH-DOWN-MAX(h, i):
    if i has children then:
        m := index of the largest child or grandchild of i
        if m is a grandchild of i then:
            if h[m] > h[i] then:
                swap h[m] and h[i]
                if h[m] < h[parent(m)] then:
                    swap h[m] and h[parent(m)]
                endif
                PUSH-DOWN(h, m)
            endif
        else if h[m] > h[i] then:
            swap h[m] and h[i]
        endif 
    endif

Итеративная форма

Поскольку рекурсивный вызов push-down-min и push-down-max находятся в хвостовой позиции, эти функции можно тривиально преобразовать в чисто итеративные формы, выполняющиеся в постоянном пространстве:

function PUSH-DOWN-ITER(h, m):
    while m has children then:
        i := m
        if i is on a min level then:
            m := index of the smallest child or grandchild of i
            if h[m] < h[i] then:
                swap h[m] and h[i]
                if m is a grandchild of i then:
                    if h[m] > h[parent(m)] then:
                        swap h[m] and h[parent(m)]
                    endif
                else
                    break
                endif
            else
                break 
            endif
        else:
            m := index of the largest child or grandchild of i
            if h[m] > h[i] then:
                swap h[m] and h[i]
                if m is a grandchild of i then:
                    if h[m] < h[parent(m)] then:
                        swap h[m] and h[parent(m)]
                    endif
                else
                    break
                endif
            else
                break 
            endif
        endif
    endwhile

Вставка

Чтобы добавить элемент в кучу min-max, выполните следующие операции:

Добавьте необходимый ключ в (конец) массива, представляющего минимальную-максимальную кучу. Это, скорее всего, нарушит минимальные и максимальные свойства кучи, поэтому нам необходимо настроить куча.
Сравните новый ключ с его родительским:
1. Если окажется, что он меньше (больше), чем родительский, то он наверняка меньше (больше), чем все остальные узлы на максимальных (минимальных) уровнях, которые находятся на пути к корню кучи. Теперь просто проверьте узлы на минимальном (максимальном) уровне.
2. Путь от нового узла до корня (с учетом только минимальных (максимальных) уровней) должен идти в порядке убывания (возрастания), как это было до вставки. Итак, нам нужно произвести бинарную вставку нового узла в эту последовательность. Технически проще поменять новый узел с его родителем, пока родительский узел больше (меньше).

Этот процесс реализуется вызовом push-up алгоритм, описанный ниже, для индекса вновь добавленного ключа.

Пуш-ап

The push-up алгоритм (или bubble-up как это называется в ^[7] ) выглядит следующим образом:

function PUSH-UP(h, i):
    if i is not the root then:
        if i is on a min level then:
            if h[i] > h[parent(i)] then:
                swap h[i] and h[parent(i)]
                PUSH-UP-MAX(h, parent(i))
            else:
                PUSH-UP-MIN(h, i)
            endif
        else:
            if h[i] < h[parent(i)] then:
                swap h[i] and h[parent(i)]
                PUSH-UP-MIN(h, parent(i))
            else:
                PUSH-UP-MAX(h, i)
            endif
        endif
    endif

Отжимание мин.

function PUSH-UP-MIN(h, i):
    if i has a grandparent and h[i] < h[grandparent(i)] then:
        swap h[i] and h[grandparent(i)]
        PUSH-UP-MIN(h, grandparent(i))
    endif

Пуш-ап Макс

Как и в случае push-down операции, push-up-max идентичен push-up-min, но с обратными операторами сравнения:

function PUSH-UP-MAX(h, i):
    if i has a grandparent and h[i] > h[grandparent(i)] then:
        swap h[i] and h[grandparent(i)]
        PUSH-UP-MAX(h, grandparent(i))
    endif

Итеративная форма

Поскольку рекурсивные вызовы push-up-min и push-up-max находятся в хвостовой позиции, эти функции также можно тривиально преобразовать в чисто итеративные формы, выполняющиеся в постоянном пространстве:

function PUSH-UP-MIN-ITER(h, i):
    while i has a grandparent and h[i] < h[grandparent(i)] then:
        swap h[i] and h[grandparent(i)]
        i := grandparent(i)
    endwhile

Пример

Вот один пример вставки элемента в кучу Min-Max.

Предположим, у нас есть следующая куча min-max и мы хотим вставить новый узел со значением 6.

Первоначально узел 6 вставляется как правый дочерний элемент узла 11. 6 меньше 11, поэтому он меньше всех узлов на максимальных уровнях (41), и нам нужно проверить только минимальные уровни (8 и 11). ). Мы должны поменять местами узлы 6 и 11, а затем поменять местами 6 и 8. Таким образом, 6 перемещается в корневую позицию кучи, бывший корень 8 перемещается вниз, чтобы заменить 11, а 11 становится правым дочерним элементом 8.

Рассмотрите возможность добавления нового узла 81 вместо узла 6. Первоначально узел вставляется как правый дочерний узел узла 11. 81 больше, чем 11, поэтому он больше, чем любой узел на любом из минимальных уровней (8 и 11). Теперь нам нужно только проверить узлы на максимальных уровнях (41) и сделать одну замену.

Найти минимум

Минимальный узел (или минимальный узел в случае дублирования ключей) Min-Max Heap всегда расположен в корне. Таким образом, найти минимум — это тривиальная операция с постоянным временем, которая просто возвращает корни.

Найти максимум

Максимальный узел (или максимальный узел в случае повторяющихся ключей) Min-Max Heap, который содержит более одного узла, всегда расположен на первом максимальном уровне, то есть как один из непосредственных дочерних элементов корня. Таким образом, поиск максимума требует не более одного сравнения, чтобы определить, какой из двух дочерних элементов корня больше, и поэтому также является операцией с постоянным временем. Если куча Min-Max содержит один узел, то этот узел является максимальным узлом.

Удалить минимум

Удаление минимума — это всего лишь частный случай удаления произвольного узла, индекс которого в массиве известен. В этом случае последний элемент массива удаляется (уменьшается длина массива) и используется для замены корня в начале массива. push-down затем вызывается для корневого индекса для восстановления свойства кучи в $O(\log _{2}(n))$ время.

Удалить максимум

Удаление максимума — это снова частный случай удаления произвольного узла с известным индексом. Как и в операции «Найти максимум», требуется одно сравнение для определения максимального дочернего элемента корня, после чего он заменяется последним элементом массива и push-down затем вызывается по индексу замененного максимума для восстановления свойства кучи.

Расширения

Куча min-max-median — это вариант кучи min-max, предложенный в оригинальной публикации о структуре, который поддерживает операции дерева статистики порядка .

Ссылки

^ Мишель. «Джим» . Переполнение стека . Проверено 8 сентября 2016 г.
^ Перейти обратно: ^а ^б АТКИНСОН, доктор медицины; САК, младший; САНТОРО, Н.; СТРОТОТТ, Т. (1986). Манро, Ян (ред.). «Мин-макс кучи и очереди с обобщенным приоритетом» (PDF) . Коммуникации АКМ . 29 (10): 996–1000. дои : 10.1145/6617.6621 . S2CID 3090797 .
^ АТКИНСОН, доктор медицины; САК, младший; САНТОРО, Н.; СТРОТОТТ, Т. (1986). Манро, Ян (ред.). «Мин-макс кучи и очереди с обобщенным приоритетом» (PDF) . Коммуникации АКМ . 29 (10): 996–1000. дои : 10.1145/6617.6621 . S2CID 3090797 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж АТКИНСОН, доктор медицины; САК, младший; САНТОРО, Н.; СТРОТОТТ, Т. (1986). Манро, Ян (ред.). «Мин-макс кучи и очереди с обобщенным приоритетом» (PDF) . Коммуникации АКМ . 29 (10): 996–1000. дои : 10.1145/6617.6621 . S2CID 3090797 .
^ Гонне, Гастон Х.; Баеза-Йейтс, Рикардо (1991). Справочник по алгоритмам и структурам данных: на языках Pascal и C. ISBN 0201416077 .
^ К. Папаррисос, Иоаннис (2011). «Жесткая граница наихудшего числа сравнений для алгоритма построения кучи Флойда». arXiv : 1012.0956 . Бибкод : 2010arXiv1012.0956P . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ АТКИНСОН, доктор медицины; САК, младший; САНТОРО, Н.; СТРОТОТТ, Т. (1986). Манро, Ян (ред.). «Мин-макс кучи и очереди с обобщенным приоритетом» (PDF) . Коммуникации АКМ . 29 (10): 996–1000. дои : 10.1145/6617.6621 . S2CID 3090797 .

[How_to_perform_a_general_deletion_operation_on_a_min-max_heap?-1] Мишель. «Джим» . Переполнение стека . Проверено 8 сентября 2016 г.

[:0-2] Перейти обратно: ^а ^б АТКИНСОН, доктор медицины; САК, младший; САНТОРО, Н.; СТРОТОТТ, Т. (1986). Манро, Ян (ред.). «Мин-макс кучи и очереди с обобщенным приоритетом» (PDF) . Коммуникации АКМ . 29 (10): 996–1000. дои : 10.1145/6617.6621 . S2CID 3090797 .

[3] АТКИНСОН, доктор медицины; САК, младший; САНТОРО, Н.; СТРОТОТТ, Т. (1986). Манро, Ян (ред.). «Мин-макс кучи и очереди с обобщенным приоритетом» (PDF) . Коммуникации АКМ . 29 (10): 996–1000. дои : 10.1145/6617.6621 . S2CID 3090797 .

[:1-4] Перейти обратно: ^а ^б ^с ^д ^и ^ж АТКИНСОН, доктор медицины; САК, младший; САНТОРО, Н.; СТРОТОТТ, Т. (1986). Манро, Ян (ред.). «Мин-макс кучи и очереди с обобщенным приоритетом» (PDF) . Коммуникации АКМ . 29 (10): 996–1000. дои : 10.1145/6617.6621 . S2CID 3090797 .

[5] Гонне, Гастон Х.; Баеза-Йейтс, Рикардо (1991). Справочник по алгоритмам и структурам данных: на языках Pascal и C. ISBN 0201416077 .

[6] К. Папаррисос, Иоаннис (2011). «Жесткая граница наихудшего числа сравнений для алгоритма построения кучи Флойда». arXiv : 1012.0956 . Бибкод : 2010arXiv1012.0956P . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[7] АТКИНСОН, доктор медицины; САК, младший; САНТОРО, Н.; СТРОТОТТ, Т. (1986). Манро, Ян (ред.). «Мин-макс кучи и очереди с обобщенным приоритетом» (PDF) . Коммуникации АКМ . 29 (10): 996–1000. дои : 10.1145/6617.6621 . S2CID 3090797 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]