TwiddleLab / Код / Структуры данных, которые видно

Кучи и очереди с приоритетом

Урок 8 из 10 · 7 мин · Бесплатно, без аккаунта

Что ты узнаешь

• Очередь с приоритетом выдаёт сначала самый срочный элемент, а не самый старый.
• Куча делает это деревом, где каждый родитель не менее срочный, чем его дети, поэтому наверху всегда самый срочный.
• Вставка: добавь в конец и поднимай, пока он важнее родителя. Взятие: последний элемент прыгает наверх и опускается. Несколько обменов, один путь.
• Дерево живёт в простом списке: родитель i это (i - 1) // 2, дети это 2i + 1 и 2i + 2.

Начать урок

Как идёт урок

1. В игре ждут события. Какое случится следующим?

   Не самое старое, а самое срочное. Меньше число = срочнее. Нажми на следующее, три раза.

2. Куча, где самое срочное всплывает наверх.

   Каждый родитель должен быть срочнее своих детей. Новое событие встаёт вниз: поднимай его, пока нужно.

   После обмена бывший родитель оказывается под новым узлом, который его важнее, а другого своего ребёнка он и так был важнее. Поэтому правило выполняется везде, кроме, может быть, места между новым узлом и его новым родителем. Проверь там и повтори.

3. Дерево на самом деле список.

   Прочитай дерево ряд за рядом, слева направо, и получится список внизу. Найди узлы в списке.

4. Куча как очередь с приоритетом.

   Очередь с приоритетом всегда выдаёт следующим самый срочный элемент. Куча это обычный способ её построить.

   Правило кучи: каждый родитель не менее срочный, чем его дети. Поэтому верх, индекс 0, самый срочный.

   Она хранится в списке: родитель i это (i - 1) // 2, дети это 2i + 1 и 2i + 2. Вставка поднимает, взятие опускает.

5. Обслужи самое срочное событие.

   Верх уходит. Последний элемент прыгает на его место. Опускай его, пока правило снова не выполнится.

6. Шторм событий.

   События приходят и обслуживаются вперемешку. Держи кучу кучей. Мало промахов даёт звёзды.

7. Напиши всплытие.

   1 только что добавили в конец кучи. Поднимай её, пока она важнее родителя.

8. Как ИИ в игре находит путь: A*.

   A* держит клетки, которые может исследовать, в куче и всегда берёт лучшую. Побудь кучей: выбери клетку, которую он исследует следующей.

9. Твой код строит кучу.

   Приходят семь событий. Твоё всплытие из прошлого шага ставит каждое на место.

Предыдущий урок: Двоичные деревья поиска · Следующий урок: Выбираем подходящую структуру · Часть курса: Структуры данных, которые видно

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.