Изменение кучи за время O(lgn)

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

Пусть A — мини-куча. Операция HEAP-MODIFY(A, i, k) изменяет ключ в узле i на новое значение k, затем переставляет элементы в минимальной куче. Приведите реализацию HEAPMODIFY, которая выполняется за время O(lgn) для минимальной кучи из n элементов.

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

HEAP-MODIFY(A,i,k):
    A[i] = K

    if A[i] < A[i/2]
        while A[i] < A[i/2] and i > 1
            exchange A[i], A[i/2]
            i=i/2
    else if A[i] > A[2*i]
    while A[i] > A[2*1] and i <k
        exchange A[i], A[2*i]
        i = 2*1

Любые предложения относительно того, как это можно решить?


algorithm heap heapsort
person bittwiddler    schedule 22.02.2011    source источник
comment
O (lg(n)) — это код для разделяй и властвуй. Вам нужно разделить проблему на две части: одну, которая уже решена, и одну, которую нужно решить. Поскольку уже решено, делать нечего. Правильно ли работает ваш алгоритм «разделяй и властвуй»? Обновите свой вопрос, чтобы объяснить, как вы разделяете и властвуете, чтобы мы могли это прокомментировать.   -  person S.Lott    schedule 22.02.2011

Ответы (3)


arrow_upward
1
arrow_downward 

HEAP-MODIFY(A,i,K) 
A[i] = K 
MIN-HEAPIFY(A,1)

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

person PinkMetroid    schedule 22.02.2011
comment
Видите ли, это тоже был мой первый инстинкт. Команда A[i] = K является постоянной операцией, а MIN-HEAPIFY — операцией O(lg(n)). - person bittwiddler; 22.02.2011

arrow_upward
3
arrow_downward

Вы думаете в правильном направлении, но операции, которые вы выполняете, не гарантируют в результате min-heap. Посмотрите на следующую кучу:

  ..
  11
 /  \
19  63 (<-was 13)
.. /  \
  55  15
  ..  ..

Представьте, что вы только что обновили ключ 13 до 63 и хотите восстановить свойство min-heap. Ваш код поменял бы местами 55 и 63, потому что 55‹63, но тогда 55 будет родителем 63 и 15(!) и, следовательно, повредит свойству min-heap.

Нужная вам функция (для восстановления свойства min-heap) называется "heapify". Это не тривиально, но и не очень сложно. Посмотрите его объяснение в этой статье Википедии о heapsort. Нет ничего плохого в том, чтобы просто прочитать/изучить решение, если вы его понимаете, а не просто копируете.

Если после этого у вас останутся вопросы, спрашивайте.

person Dave O.    schedule 22.02.2011
comment
Спасибо! У меня было ощущение, что я должен использовать MIN-HEAPIFY, так как он работает на O(lg(n)), но это было слишком просто. Однако в задаче нет никаких ограничений. В любом случае, мне все еще нужно сесть и подумать об этом и действительно понять это. - person bittwiddler; 22.02.2011
comment
@saullawl, функцию heapify действительно несложно понять: она в основном делает то, что делал ваш код: перемещает ключи вверх, если они меньше, чем их родители (потому что именно так определяется минимальная куча). Это просто для того, чтобы вы упустили из виду, что, перемещая ключи вверх, вы можете повредить свойство min-heap в новых местах, где оно выполнялось раньше. Так что куча ремонтов этих деталей. - person Dave O.; 22.02.2011
comment
Первоначально у меня было следующее: HEAP-MODIFY(A,i,K) A[i] = K MIN-HEAPIFY(A,1) Был ли я перепроектирован? - person bittwiddler; 22.02.2011

arrow_upward
3
arrow_downward

Вы можете найти и удалить Node(i), изменить значение Node на k и вернуть его в кучу. Это не самый эффективный способ, но все же log(n). Преимущество заключается в том, что это просто и, вероятно, будет повторно использовать операции, которые вы уже реализовали.

person kefeizhou    schedule 22.02.2011