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