Как удалить минимальный ключ в максимальной куче?

Question

Мне нужно реализовать функцию HEAP-DELETE-MIN(Array), которая удаляет самое низкое целое число в максимальной куче. Я не спрашиваю о самой функции, но кто-то может предоставить мне какой-нибудь псевдокод, чтобы помочь мне начать работу? Это было бы очень полезно. Массив должен оставаться максимальной кучей в конце функции.

Answer 1

По сути, вам нужно будет выполнить поиск по всем конечным узлам неявной кучи, хранящейся в массиве. Это будет листовой узел кучи, потому что его родитель должен быть больше его (свойство max heap), и мы знаем, что листья хранятся по индексу n/2 и далее (хотя это не повредит нашей алгоритмической сложности). По сути, вы должны сделать следующее:

1) Search the array for the minimum element
2) Place the last-inserted heap element in the position of the minimum element (essentially this is the delete)
3) Upheap the replaced node to restore maximum heap property and correct storage of the heap in the array

Для поиска минимального элемента потребуется O(n), затем для коммутатора O(1) и, наконец, O(log n) для повышения. В целом это линейное время, по сути, лучшее, что вы можете сделать.

Не забудьте соблюдать осторожность при выполнении операций с индексами, 2*i - левый потомок узла i, а 2*i+1 - правый потомок узла i в куче на основе массива (при условии, что 0-й элемент массива всегда пуст, а корень кучи находится по индексу 1)