Визуализация Бипа: менее известный, но увлекательный вариант кучи
4 июня 2025 г.Если вы знакомы с кучами, вы, вероятно, использовали их в очереди приоритетных, Heapsort или, может быть, даже для решения этих сложных проблем DSA. Но вы когда -нибудь слышали оБип?
Бип выступает заБи-паритарная куча- Умная структура, введенная Яном Мунро и Хендрой Сувандой в 1984 году. Она предназначена для эффективности как вставки, так и поисковых операций, что дает нам сложность времени O (√n) для обоих.
В этой истории мы рассмотрим:
- 🧱 Что отличает Бип от обычной кучи
- 🧠 Как работают основные операции, такие как вставка, извлечение, поиск и майн/максимальный
- 🎥 И, конечно,анимированные визуализацииЧтобы помочь воплотить эти концепции в жизнь
🆚 Кучи против Бипа: В чем разница?
Кучи-это приоритетная очередь и сортировки, но они следуют строгой модели бинарного дерева: у каждого узела есть не более одного родителя и двух детей, и свойство кучи гарантирует, что родитель меньше (в минимальном) или больше (в максимальном HEAP), чем его дети.
Биты переверните эту идею, организуя элементы вТреугольная матрица, где узлы, кроме границ, могут иметь двух родителей и двое детей. Эта структура обеспечивает элегантное, похожее на сетку представление, которое делает поисковые операции гораздо более эффективными.
Особенность | Двоичная куча | Бип |
|---|---|---|
Структура | Бинарное дерево | Треугольная матрица |
Родители на узел | 1 | До 2 |
Дети на узел | До 2 | До 2 |
Сложность поиска | На) | O (√n) |
Вставить сложность | O (log n) | O (√n) |
Варианты использования | Heapsort, pqs | Быстрый поиск + вставка |
Этот макет треугольной матрицы позволяет поиску начинаться с левого нижнего левого и разумно на основе сравнений.
📌 Вот диаграмма, чтобы помочь вам визуализировать бип:
📖 Узнайте больше о Википедии
🔧 Основные операции (с GIF)
Давайте пройдемся через то, как работает каждая операция - и да, мы их оживили, чтобы вам не приходилось представлять гимнастику Повествования.
🔼 Вставьте
Мы вставляем элемент в следующую доступную позицию треугольника, затемпузырьтьсравнивая его с двумя родителями (если они существуют).
🔽 Извлечение мин
В Mine-Meap самый маленький элемент всегда наверху. Удаление это означает замену его последним элементом, а затемпузырясь внизПолем
🔍 Поиск
Поиск - это то, где сияют Бичи. Начните с левого дна и в зависимости от сравнений, двигайтесь вверх или вправо. Сложность времени:O (√n)Полем
⬇ min & ⬆ Макс
- Минвсегда в корне.
- Максимумнаходится на последнем уровне (правый нижний угол).
🎓 Завертывание
Бичи могут не быть частью стандартного алгоритма инструментария, но они предлагают убедительную смесь структуры и производительности. Их уникальный дизайн и поисковая механика заставляют их достойно изучить, независимо от того, глубоко ли вы в теории структуры данных или просто любопытны альтернативы обычной куче.
Если вы заинтересованы в проверке полного кода и визуальных демонстраций, вы можете найти их наGitHubПолем
Оригинал