об алгоритме make_heap в C ++

Question

http://www.cplusplus.com/reference/algorithm/make_heap/

По этой ссылке.он говорит:

Внутренне, куча - это дерево, где каждый узел ссылается на значения, не превышающие его собственного значения.В кучах, сгенерированных make_heap, конкретная позиция элемента в дереве, а не определяемая ссылками, занимающими память, определяется его абсолютной позицией в последовательности, где * first всегда является самым высоким значением в куче.

о «определяется его абсолютным положением в последовательности».Я запутался здесь.В нем также говорится, что «куча - это дерево, где каждый узел связан со значениями, не превышающими его собственное значение»

Противопоставлены ли эти два предложения?ТАК запутался здесь.Какое именно дерево для кучи в C ++?

Жаль, что любой добрый человек может мне помочь Спасибо большое

Answer 1

Это говорит о том, что куча имеет типичную древовидную структуру, где каждый «родительский» узел больше или равен значению «дочернего» узла («... где каждый узел связан со значениями не более»чем его собственное значение ... ").

Далее говорится, что вместо использования ссылок (то есть указателей, скажем, в структуре (как вы бы использовали для связанного списка)), он используетоперативная память (иначе называемая массивом - «... определяется ее абсолютным положением в последовательности ...»).

* первый - это первый элемент (или самый большой / самый маленький, в зависимости от функции компаратора) в куче, и он всегда находится в [0] -ом индексе массива.Для каждого индекса i дети расположены в [2 * i + 1] и [2 * i + 2].

Надеюсь, это поможет.

Answer 2

Если вы посмотрите на реализации кучи, вы увидите, что дерево реализовано в виде массива. Вы можете найти значения ниже узла в индексе i в индексах 2 * i+1 и 2 * i +2. Так что это дерево, где вы можете получить доступ к элементам по их абсолютной позиции в массиве.