Я запутался, решая следующую проблему (вопросы 1–3).
Вопрос
Д -ичные куч, как двоичные кучи, но (с одним возможным исключением) узлы без листьев имеют d детей вместо 2 -х детей.
Как бы вы представили d -ary кучу в массиве?
Какова высота d- дневной кучи из n элементов в терминах n и d ?
Дайте эффективную реализацию EXTRACT-MAX в d -ary max-heap. Проанализируйте время его работы с точки зрения d и n .
Дайте эффективную реализацию INSERT в d -ary max-heap. Проанализируйте время его работы с точки зрения d и n .
Дайте эффективную реализацию INCREASE-KEY ( A , i , k ), которая помечает ошибку, если k <A [i] = k, и затем соответствующим образом обновляет структуру кучи d- матрицы. Проанализируйте время его работы с точки зрения d и n .
Мое решение
Дайте массив
→ Моя запись кажется немного сложной. Есть ли другой, более простой?
Пусть h обозначает высоту d -ой кучи.
Предположим, что куча представляет собой полное d -ное дерево
Это моя реализация:
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:
→ Это эффективное решение? Или в моем решении что-то не так?
h = (log [nd−1+1])− 1
таким образом, мы выше объяснение высоты не будет выполняться. h = log [nd − 1 + 1] −1 = log [nd] -1 = log [n] Несмотря на то, что высота дерева записывается какΘ(log(n)).
Примечание: log всегда находится в базе d для d-ary-кучи ,Ответы:
Ваше решение действительно и соответствует определению d -ary heap. Но, как вы указали, ваши обозначения немного сложны.
Вы можете использовать эти две следующие функции для получения родительского элемента i-го элемента и j-го дочернего элемента i-го элемента.
Книга CLRS уже предоставляет процедуру INSERT. Который выглядит так:
Как и INSERT, INCREASE-KEY также определен в учебнике как:
источник
источник
Ответ на второй вопрос: h = log d (n (d-1) + 1) - 1 Итак, h = log d (nd - n + 1) - 1
источник