Косая биномиальная куча

От / / Оставьте комментарий

Косая биномиальная куча Косая биномиальная куча Структура данных для операций с приоритетными очередями   Поддерживает операции вставки с постоянным временем   Основана […]

'Кучи (структуры данных)', 'Приоритетные очереди', Heaps (data structures), Priority queues

Косая биномиальная куча

  • Косая биномиальная куча

    • Структура данных для операций с приоритетными очередями  
    • Поддерживает операции вставки с постоянным временем  
    • Основана на косой двоичной системе счисления  

  • Структура

    • Лес косых биномиальных деревьев  
    • Косое биномиальное дерево ранга 0 — одноэлементный узел  
    • Простая ссылка связывает два дерева ранга r  
    • Косая связь типа А связывает три дерева  
    • Косая связь типа B связывает дерево ранга 0 и дерево ранга r  

  • Операции

    • Найти-минимум: O(log n) время  
    • Поглощать: O(log n) время  
    • Вставить: O(1) время  
    • Удалить-минимум: O(log n) время  
    • Клавиша уменьшения: O(log n) время  

  • Оптимизация

    • Бродал и Окасаки предложили технику «начальной загрузки»  
    • Временная сложность слияния снижена до O(1)  
    • Метод применим к любой приоритетной очереди с постоянной временной вставкой и логарифмическим объединением  

Полный текст статьи:

Косая биномиальная куча

Похожие статьи:

  1. B-дерево — Arc.Ask3.Ru B-дерево История и определение B-деревьев B-деревья были изобретены Рудольфом Байером и Эдвардом М. Маккрайтом в 1970...
  2. Развернутое дерево Раскидистое дерево Развернутое дерево Бинарное дерево поиска с дополнительным свойством быстрого доступа к недавно использованным элементам.  ...
  3. Косая куча Косая куча Косая куча Структура данных кучи, реализованная в виде бинарного дерева   Выгодна из-за способности объединяться...
  4. 2000 2000 Основные события 2000 года 1 января: Вступление в должность президента США Джорджа У. Буша.  11...
  5. д-арная куча Большая куча Двоичная куча и d-heap Двоичная куча — это 2-кучная, троичная куча — 3-кучная.   Изобретена...
  6. Биномиальная куча Биномиальная куча Определение и свойства биномиальной кучи Биномиальная куча — это структура данных, которая поддерживает операции...
  7. Куча сопряжений — Arc.Ask3.Ru Куча спариваний Описание парных куч Парные кучи — это упорядоченные по кучам многоходовые древовидные структуры.   Они...
  8. Куча (математика) Куча (математика) Полугруппа — алгебраическая структура с троичной операцией.  Куча — полугруппа, каждый элемент которой является...
  9. Клавиша создания Клавиша составления История и значение клавиши compose Клавиша compose была введена в 1963 году для упрощения...
  10. Куча Фибоначчи Куча Фибоначчи Структура кучи Фибоначчи Куча Фибоначчи состоит из набора упорядоченных деревьев, удовлетворяющих свойству минимальной кучи.  ...
  11. Бродал очередь — Arc.Ask3.Ru Очередь Бродаля Очередь Бродала Структура очереди с кучей/приоритетом   Низкие временные рамки в наихудшем случае: O(1) для...
  12. Дерево АВЛ Дерево AVL Определение и свойства дерева AVL Дерево AVL — самобалансирующееся бинарное дерево поиска.   Высоты дочерних...
  13. Дерево интервалов Дерево интервалов Дерево интервалов Древовидная структура данных для хранения интервалов   Эффективно находит интервалы, пересекающие заданный интервал...
  14. Оптимальное двоичное дерево поиска Optimal binary search tree Оптимальные бинарные деревья поиска Оптимальные бинарные деревья поиска (Optimal BST) минимизируют время...
  15. B-дерево B-дерево Основы B-дерева B-дерево — это древовидная структура данных, используемая для эффективного хранения и поиска данных. ...
  16. Двоичная куча Двоичная куча Определение и свойства двоичной кучи Двоичная куча — это полное двоичное дерево с упорядоченными...
  17. Биномиальная теорема Биномиальная теорема Биномиальная теорема связывает коэффициенты разложения биномиального выражения с количеством способов разбиения набора элементов на...
  18. Левое дерево Левое дерево Определение и свойства левого дерева Левое дерево (левая куча) — приоритетная очередь, реализованная с...
  19. Дерево Фенвик Дерево Фенвик Основы дерева Фенвика Дерево Фенвика — это структура данных для эффективного вычисления сумм префиксов...
  20. Слэш (пунктуация) Косая черта (знак препинания) Косая черта (/) используется в различных контекстах, включая математику, программирование, комментарии, валюты...
  21. Дерево козла отпущения Дерево козлов отпущения История и основные характеристики Дерево козлов отпущения изобретено Арне Андерссоном в 1989 году...
  22. Куча (структура данных) Куча (структура данных) Определение и свойства кучи Куча — это структура данных, которая поддерживает операции с...

Оставьте комментарий

Прокрутить вверх