Модификация кучи за время O (lgn) - PullRequest
Новая
       12

Модификация кучи за время O (lgn)

6 голосов
/ 22 февраля 2011

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

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

Поскольку мы должны разработать алгоритм, который выполняется за время 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

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

Ответы [ 3 ]

3 голосов
/ 22 февраля 2011

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

3 голосов
/ 22 февраля 2011

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

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

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

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

Если после этого у вас все еще есть вопросы, задавайте.

1 голос
/ 22 февраля 2011 
HEAP-MODIFY(A,i,K) 
A[i] = K 
MIN-HEAPIFY(A,1)

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

...