Мне нужно реализовать функцию HEAP-DELETE-MIN(Array), которая удаляет наименьшее целое число в максимальной куче. Я не прошу саму функцию, но может ли кто-нибудь дать мне какой-нибудь псевдокод, чтобы помочь мне начать работу? Это было бы большим подспорьем. Массив должен оставаться максимальной кучей в конце функции.
Как удалить минимальный ключ в максимальной куче?
Ответы (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) для upheap. В целом это линейное время, по сути, лучшее, что вы можете сделать.
Не забудьте быть осторожным с операциями индекса, 2*i — левый дочерний элемент узла i, а 2*i+1 — правый дочерний элемент узла i в куче на основе массива (при условии, что 0-й элемент массива всегда пуст, а корень кучи находится в индексе 1)
person
pippin1289
schedule
19.02.2013
