Два решения для увеличения значения всех листовых элементов

Я хочу увеличить значение всех элементов листа. Все с индексом больше *floor[n/2].

1) Вызовите HEAP-INCREASE-KEY(A,i,key) для каждого листового элемента

2) Увеличьте ключ каждого листового элемента до нового значения, затем вызовите BUILD-MAX-HEAP(A)

Какой способ будет эффективнее и почему?

Немного дополнительной информации. Каждый вызов Max-Heapify стоит O(lgn) времени, а Build-max-heap делает O(n) таких вызовов. Таким образом, время выполнения равно O(nlgn). Время работы Heap-Increase-Key равно O(lgn).

HEAP-INCREASE-KEY(A,i,key)

if key<A[i]
  error "new key is smaller than current key.
A[i]
while i>1 and A[Parent(i)]<A[i]
  exchange A[i] with A[Parent(i)]
  i=Parent()

СТРОЙКА-МАКСИМАЛЬНАЯ КУЧА(A)

A.heap-size = A.length
for i = *floor[A.length/2] downto 1
    MAX-HEAPIFY(A,i)

если вам нужно знать, что такое max-heapify

MAX-HEAPIFY(A,i)

l=Left(i)
r=Right(i)
if l<=A.heap-size and A[l] > A[i]
   largest = l
else largest = i 
if r<=A.heap-size and A[r] > A[largest]
  largest = r
if largest not equal i
   exchange A[i] with A[largest]
   MAX-HEAPIFY (A.largest)

java algorithm big-o heapsort
person GiBiT 09    schedule 10.10.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Второй более эффективен.

1) Вызовите HEAP-INCREASE-KEY(A,i,key) для каждого листового элемента

Количество листовых элементов равно O(n). Время HEAP-INCREASE-KEY(A,i,key) O(lgn). Таким образом, временная сложность первого решения равна O(nlgn).

2) Увеличьте ключ каждого листового элемента до нового значения, затем вызовите BUILD-MAX-HEAP(A)

Для создания кучи с нуля требуется только линейное время. Таким образом, временная сложность второго решения равна O(n).

Немного дополнительной информации. Каждый вызов Max-Heapify стоит O(lgn) времени, а Build-max-heap делает O(n) таких вызовов. Таким образом, время выполнения равно O(nlgn).

Если это утверждение было предоставлено в вашем домашнем задании, то временные сложности для обоих решений одинаковы. Однако вы можете построить максимальную кучу за линейное время, а не за O(nlgn) времени. .

person Terry Li    schedule 10.10.2013
comment
Это утверждение было дано в книге. - person GiBiT 09; 10.10.2013
comment
То есть, если у них у всех индекс больше, чем *floor[n/2], это ни на что не влияет? - person GiBiT 09; 10.10.2013
comment
@ GiBiT09 GiBiT09 Я думаю, что это условие выполняется для любых листовых элементов. - person Terry Li; 10.10.2013
comment
@ GiBiT09 Нет проблем. Дайте мне знать, что ваш профессор думает позже :) - person Terry Li; 10.10.2013
comment
@GiBiT09 GiBiT09 Кстати, было бы лучше добавить языковые теги, чтобы ваш вопрос мог привлечь больше внимания. - person Terry Li; 10.10.2013