Проблема с кучей файлов из CLRS

10

Я запутался, решая следующую проблему (вопросы 1–3).

Вопрос

Д -ичные куч, как двоичные кучи, но (с одним возможным исключением) узлы без листьев имеют d детей вместо 2 -х детей.

  1. Как бы вы представили d -ary кучу в массиве?

  2. Какова высота d- дневной кучи из n элементов в терминах n и d ?

  3. Дайте эффективную реализацию EXTRACT-MAX в d -ary max-heap. Проанализируйте время его работы с точки зрения d и n .

  4. Дайте эффективную реализацию INSERT в d -ary max-heap. Проанализируйте время его работы с точки зрения d и n .

  5. Дайте эффективную реализацию INCREASE-KEY ( A , i , k ), которая помечает ошибку, если k <A [i] = k, и затем соответствующим образом обновляет структуру кучи d- матрицы. Проанализируйте время его работы с точки зрения d и n .

Мое решение

  1. Дайте массив A[a1..an]

    root:a1level 1:a2a2+d1level 2:a2+da2+d+d21level k:a2+i=1k1dia2+i=1kdi1

    Моя запись кажется немного сложной. Есть ли другой, более простой?

  2. Пусть h обозначает высоту d -ой кучи.

    Предположим, что куча представляет собой полное d -ное дерево

    1+d+d2+..+dh=ndh+11d1=nh=logd[nd1+1]1
  3. Это моя реализация:

    EXTRACT-MAX(A)
    1  if A.heapsize < 1
    2      error "heap underflow"
    3  max = A[1]
    4  A[1] = A[A.heapsize]
    5  A.heap-size = A.heap-size - 1
    6  MAX-HEAPIFY(A, 1)
    7  return max
    
    MAX-HEAPIFY(A, i)
    1  assign depthk-children to AUX[1..d]
    2  for k=1 to d
    3      compare A[i] with AUX[k]
    4      if A[i] <= AUX[k]
    5          exchange A[i] with AUX[k]
    6          k = largest
    7  assign AUX[1..d] back to A[depthk-children]
    8  if largest != i
    9      MAX-HEAPIFY(A, (2+(1+d+d^2+..+d^{k-1})+(largest-1) )
    
    • Время работы MAX-HEAPIFY:

      TM=d(c8d+(c9+..+c13)d+c14d)
      ci
    • TE=(c1+..+c7)+TMCdh=Cd(logd[n(d1)+1]1)=O(dlogd[n(d1)])

    Это эффективное решение? Или в моем решении что-то не так?

lucasKo
источник
Я думаю, что в этом вопросе есть небольшая ошибка, так же как и в объяснении: высота d-арной кучи достигает h = (log [nd - n + 1]) - 1 // ЗАМЕЧАТЬ его «-n», а не «-1», а не h = (log [nd−1+1])− 1таким образом, мы выше объяснение высоты не будет выполняться. h = log [nd − 1 + 1] −1 = log [nd] -1 = log [n] Несмотря на то, что высота дерева записывается как Θ(log(n)).Примечание: log всегда находится в базе d для d-ary-кучи ,
Сурабхи Радж

Ответы:

10
  1. Ваше решение действительно и соответствует определению d -ary heap. Но, как вы указали, ваши обозначения немного сложны.

    Вы можете использовать эти две следующие функции для получения родительского элемента i-го элемента и j-го дочернего элемента i-го элемента.

    d-ary-parent(i)    return (i2)/d+1

    d-ary-child(i,j)    return d(i1)+j+1

    1jdd-ary-parent(d-ary-child(i,j))=i

    dd=2d2

  2. h=logd(nd1+1)1logd(nd)1=logd(n)+logd(d)1=logd(n)+11=logd(n)Θ(logd(n))

    cΘ

  3. AUXd-ary-parentd-ary-child

    EXTRACT-MAXMAX-HEAPIFYO(d logd(n(d1)))

    O(d logd(n(d1)))=O(d(logd(n)+log(d1)))=O(d logd(n)+d logd(d1))

    dndlogd(d1)O(dlogd(n))MAX-HEAPIFYOΘ

  4. Книга CLRS уже предоставляет процедуру INSERT. Который выглядит так:

    INSERT(A,key)    A.heap_size=A.heap_size+1    A[A.heap_size]=    INCREASE-KEY(A,A.heap_size,key)

    O(logd(n))

  5. Как и INSERT, INCREASE-KEY также определен в учебнике как:

    INCREASE-KEY(A,i,key)    if key<A[i]        error"new key is smaller then current"    A[i]=key    while i>1 and A[i]>A[d-ary-parent(i)]        A[i]A[d-ary-parent(i)]        i=d-ary-parent(i)

    O(logd(n))

Бартош Прзыбыльски
источник
Спасибо! Как насчет реализации INCREASE-KEY и INSERT? Я пытаюсь написать это, но он дал дважды рекурсивный вызов MAX-HEAPIFY. Есть ли лучшее решение? Я нашел мало информации в Интернете и вики
lucasKo
Это остальное упражнение? Если это так, пожалуйста, обновите свой вопрос, и я буду рад ответить на тему.
Бартош Прзыбыльски,
Я поставил эти вопросы в отредактированном посте.
LucasKo
переопределить процедуру вставки? Вы имеете в виду, что не нужно вызывать процедуру, которая корректирует порядок в куче, после вставки нового элемента? Я не понимаю ...
lucasKo
Это описание было немного неудачным, см. Изменения для уточнения.
Бартош Прзыбыльски
1

h=logd[nd1+1]1
1+d+d2+..+dh=ndh+11d1=nh=logd[n(d1)+1]1
h=Θ(logd(n))
Али Джазиб Махмуд
источник
-1

Ответ на второй вопрос: h = log d (n (d-1) + 1) - 1 Итак, h = log d (nd - n + 1) - 1

user55463
источник
4
Почему это ответ? Формула без объяснения никому не поможет.
Дэвид Ричерби