SAPT (Static Abstract Priority Tree) – это статичная древовидная структура данных, предназначенная для быстрого управления иерархическими данными с приоритетами. В основе лежит двумерный массив, где уровни представляют собой внутренние массивы, содержащие узлы с информацией о клетках, их приоритетах, и связях с родительскими и дочерними элементами.
Структура SAPT предлагает несколько профилей узлов, отличающихся объемом памяти и скоростью доступа к данным. Профили "Memory", "BalanceMemory", "BalanceSpeed" и "Speed" предоставляют пользователю возможность балансировать между эффективностью и потреблением памяти, варьируя способы хранения адресов клеток и связей между узлами. Профили Mini являются облегченными версиями, подходящими для небольших структур.
Ключевым моментом SAPT является использование фрагментации памяти, позволяющей значительно увеличить максимальный размер уровня (до триллиона элементов), при этом, за счет грамотной реализации, повышается эффективность кэширования. Структура не требует динамического перераспределения памяти, что гарантирует предсказуемую производительность. SAPT подходит для задач, где важна быстрота операций вставки, удаления (амортизированное), поиска родителя/ребенка, нахождения Min/Max элементов, а также балансировка.
SAPT обеспечивает скорость за счет заимствования преимуществ std::vector или std::array. При удалении элемента происходит простое стирание данных, что позволяет избежать дорогостоящих операций сдвига. Логика работы SAPT основана на предположении, что приоритеты узлов на одном уровне одинаковы, а на следующем уровне приоритет увеличивается на единицу, что позволяет эффективно определять уровень и автоматически балансировать структуру.
Изображение носит иллюстративный характер
Структура SAPT предлагает несколько профилей узлов, отличающихся объемом памяти и скоростью доступа к данным. Профили "Memory", "BalanceMemory", "BalanceSpeed" и "Speed" предоставляют пользователю возможность балансировать между эффективностью и потреблением памяти, варьируя способы хранения адресов клеток и связей между узлами. Профили Mini являются облегченными версиями, подходящими для небольших структур.
Ключевым моментом SAPT является использование фрагментации памяти, позволяющей значительно увеличить максимальный размер уровня (до триллиона элементов), при этом, за счет грамотной реализации, повышается эффективность кэширования. Структура не требует динамического перераспределения памяти, что гарантирует предсказуемую производительность. SAPT подходит для задач, где важна быстрота операций вставки, удаления (амортизированное), поиска родителя/ребенка, нахождения Min/Max элементов, а также балансировка.
SAPT обеспечивает скорость за счет заимствования преимуществ std::vector или std::array. При удалении элемента происходит простое стирание данных, что позволяет избежать дорогостоящих операций сдвига. Логика работы SAPT основана на предположении, что приоритеты узлов на одном уровне одинаковы, а на следующем уровне приоритет увеличивается на единицу, что позволяет эффективно определять уровень и автоматически балансировать структуру.
