Свойства d-дерева:

• Не более d^k вершин имеют глубину k
• Не более (d^k+1-1)/(d-1) вершин имеют глубину между 0 и k.
• Глубина d-дерева, содержащего n вершин, не более log_dn.

Для реализации операций над элементами полного d-дерева необходимо иметь информацию о предках и потомках d-дерева. Обозначим через Pred[i] – отца (предшественника) вершины i в d-дереве, Succ[i] – множество сыновей вершины i. По аналогии с полным бинарным деревом, d-дерево можно представить с помощью массива. Например, для d-дерева на рисунке

массив будет выглядеть следующим образом:

dHeap = { 5, 9, 8, 15, 21, 12, 16, 18, 29, 10, 31, 22, 27 }

Пусть last определяет число вершин, хранимых в массиве dHeap. В данном примере last = 13.

Описанная схема хранения обладает свойствами, позволяющими легко обращаться к отцу любой вершины и к её сыновьям:

• отец pred[i] вершины i, 0 < i < last, находится впозиции [(i-1)/d] (по соглашению о связях корень (root) находится в позиции i = 0 массива dHeap);
• сыновья вершины i находятся в позициях id+1, id+2, ..., id+d, если id + 1 < last, id + 2 < last, ..., id + d < last.

При использовании структуры данных d-кучи требуется O(1) времени для выполнения операции find_min, O(log_dn) времени для выполнения операций insert, decrease_key и O(d log_dn) времени для выполнения операций delete_min, delete и increase_key.