Является ли PHP SplHeap действительно кучей?
Является ли реализация кучи PHP полноценной реализацией?
Когда я читаю эту статью, http://en.wikipedia.org/wiki/Heap_%28data_structure%29, я понимаю, что у дочернего узла есть определенный родительский элемент, и что у родительского элемента есть определенные дочерние элементы.
Когда я смотрю на пример в документации PHP, однако, http://au.php.net/manual/en/class.splheap.php, кажется, что все дочерние узлы имеют один и тот же "уровень", но конкретный родительский / информация о детях не важна.
Например, какой узел является родительским для каждого из трех узлов, которые занимают 10-е место в примере PHP?
В моем приложении, когда пользователь выбирает "узел 156", мне нужно знать, кто его дети, чтобы каждый из них мог посещать их. (Я мог бы сделать их идентификаторы "узел 1561", "узел 1562" и т. Д., Поэтому связь очевидна).
Является ли реализация кучи PHP неполной? Должен ли я забыть класс Spl и идти своим путем? Или я что-то упускаю из-за того, как должны работать кучи? Или, возможно, я должен смотреть на конкретный вариант кучи?
Спасибо, куча!
2 ответа
API для этой реализации кучи не разрешает доступ к массиву, что вам и нужно в этом случае. Кучи, как правило, используются для реализации других структур, которые позволяют легко удалять элементы сверху.
Вы можете создать итератор оболочки, который ищет нужные вам позиции. Я подозреваю, что это будет неэффективное решение и не очень хорошее.
В этой ситуации BinaryTree это то что я думаю тебе нужно Получив место на дереве, вы можете спуститься вниз, это дети, потому что они напрямую связаны. У меня есть BinarySearchTree, который будет держать дерево в порядке, и вы можете позвонить getRoot чтобы получить копию BinaryTree, Также есть AvlTree, который будет поддерживать сбалансированное дерево для оптимального поиска.
Куча обычно используется для ответа на вопросы, которые вращаются вокруг "что такое элемент max/min в наборе".
Хотя куча может по совпадению эффективно ответить "кто является потомками узла max/min", куча не выделяется как хорошая структура данных для использования, когда вам нужно получить доступ к произвольному узлу, чтобы ответить на ваш вопрос (узел, который не максимальный узел). Это также не структура данных, которую следует использовать, если существуют определенные родительские дочерние отношения, которые необходимо представлять и поддерживать, потому что дочерние элементы могут и действительно обмениваться между различными родительскими узлами.
Таким образом, реализация кучи php определенно не является неполной по этим причинам. Вам просто нужна другая структура данных.