Изтриване в купчина, защо тази реализация превключва стойностите на последния елемент, а не просто го замества?

(USC CSCI 303 Домашна работа 4) Задача 7 (6.5-7):

Операцията Heap-Delete(A, i) изтрива елемента във възел i от купчина A. Дайте имплементация на Heap-Delete, която се изпълнява за O(lg n) време за n-елемент max-heap.

ето псевдо кода и описанието на референтното решение:

Heap-Delete(A, i)
    A[i] ↔ A[length(A)] 
    length(A) ← length(A) - 1
    Heapify(A, i)

Алгоритъмът изтрива елемента във възел i и го заменя с последния елемент. След това алгоритъмът изпълнява Heapify от възела i.

не е ли по-добре, ако "↔" беше "←" вместо това? или това наистина ли е необходимо?

Получих това от http://www-scf.usc.edu/~csci303/cs303hw4solutions.pdf (Страница 4)


performance algorithm data-structures heap pseudocode
person thedoublejointedprince    schedule 15.03.2013    source източник

Отговори (3)


arrow_upward
0
arrow_downward

Може би това се прави така, че Heap-Delete() да може да се извиква многократно по време на изпълнението на heapsort. При heapsort най-големият елемент се изважда от купчината, скрива се в последния елемент от купчината и размерът на купчината се намалява с единица. След това купчината се натрупва отново и вие продължавате към следващия по големина елемент. Крайният резултат, когато купчината е с размер 1, е, че масивът, върху който се основава купчината, е сортиран от най-малката към най-голямата. Писането на Heap-Delete() по този начин позволява Heap-Sort() да бъде много просто:

while (HeapSize>0)
   HeapDelete(0)

Сега не изглежда, че вашият Heap-Delete() следи размера на купчината извън length, което може да е доказателство срещу моята теория. Но това все пак е най-доброто ми предположение.

person angelatlarge    schedule 15.03.2013

arrow_upward
2
arrow_downward

Всъщност не е необходимо. Може би намерението е да върнете този елемент, в който случай трябва да го съхраните някъде, преди да бъде презаписан.

person Knoothe    schedule 15.03.2013

arrow_upward
-1
arrow_downward

Тук се дава само указател към основния възел, така че ако искате да изтриете и последния възел (за тези, които казват, че е необходимо o(1) за изтриване на листен възел)

Трябва да преминете през log(n), за да стигнете до листа, тогава единственият отговор е b.

person Kumar Sourabh    schedule 30.01.2017