WikiDer > Пагода (структура данных)

Pagoda (data structure)

В Информатика, а пагода это приоритетная очередь реализован с вариантом двоичное дерево. Корень указывает на своих дочерних элементов, как в двоичном дереве. Каждый другой узел указывает на своего родителя и вниз на его крайний левый (если это правый дочерний элемент) или крайний правый (если это левый дочерний элемент) лист-потомок. Основная операция - это слияние или слияние, которое поддерживает куча собственности. Элемент вставляется путем слияния его как синглтона. Корень удаляется путем объединения его правого и левого потомков. Объединение происходит снизу вверх, объединяя крайний левый край одного с крайним правым краем другого.

Рекомендации

  • J. Francon, G. Viennot и J. Vuillemin, Описание и анализ эффективного представления очереди приоритетов, Proc. 19-й ежегодный симпозиум. по основам информатики. IEEE, 1978, страницы 1–7.
  • Р. Никс, Оценка пагод, Res. Rep. 164, Департамент компьютерных наук, Йельский университет. 1988?
  • Эта статья включает материалы общественного достояния отNIST документ:Блэк, Пол Э. "пагода". Словарь алгоритмов и структур данных.