Выискивая свободное место в куче?Следить за последней вставкой?

Question

Как вы отслеживаете, где вставить в кучу: я думаю, что использование функции, которая проверяет высоту каждого поддерева, ухудшит алгоритм до O (N) с O (log N).

поэтому вы сохраняете переменную в каждом узле или переменную в куче с последней точкой вставки (определяется как?).

Answer 1

куча "почти полного" бинарного дерева.так что у вас есть только один выбор, где вы должны вставить новый элемент, проверка высоты не требуется - но указатель на местоположение, в которое должен быть вставлен следующий элемент.этого, конечно, достаточно, чтобы обеспечить высоту O (logn)