Мне интересно, разрешено ли максимальному или минимальному дереву кучи иметь повторяющиеся значения? Мне не удалось найти информацию об этом только с помощью онлайн-ресурсов.
Могут ли максимальные/минимальные деревья кучи содержать повторяющиеся значения?
Ответы (3)
Да, они могут. Вы можете прочитать об этом в «Введение в алгоритмы» (Чарльз Э. Лейзерсон, Клиффорд Стайн, Томас Х. Кормен и Рональд Ривест). Согласно определению бинарных куч в Википедии:
Все узлы либо [больше или равны](max heaps), либо [меньше или равны](min heaps) для каждого из его дочерних элементов в соответствии со сравнением предикат, определенный для кучи.
Да, они могут иметь дубликаты. Из википедии определения Куча:
Либо ключи родительских узлов всегда больше или равны ключам дочерних узлов, а наивысший ключ находится в корневом узле (такая куча называется максимальной кучей), либо ключи родительских узлов меньше или равно параметрам дочерних элементов, а самый низкий ключ находится в корневом узле (мин. куча)
Поэтому, если у них есть дочерние узлы, которые равны, это означает, что они могут дублироваться.
Да, но я бы сказал нет. Для эффективности у них не должно быть разных узлов с повторяющимися значениями, иначе он немного потеряет свою цель (вам придется искать дочерние узлы и тому подобное). Однако вы можете спроектировать каждый узел так, чтобы он содержал переменную, которая объявляет, сколько копий этого значения у вас есть в ваших данных.
Опять же это мое мнение. Если это плохой способ сделать это, я был бы рад, если бы кто-нибудь мог объяснить, почему. Возможно, мне просто нужно провести некоторые тесты эффективности. Если вы храните простые типы данных, такие как целые числа, то я бы увидел, что это менее эффективно, но для более крупных узлов объектов, у которых есть идентификаторы, это, кажется, было хорошо.