Ось готовий урок, створений спеціально для вас у стилі CS50: енергійний, зрозумілий та орієнтований на практику.

🎓 CS50 Style: Черги з пріоритетом (Priority Queues)

Привіт, друзі! 👋 Ласкаво просимо.

Сьогодні ми поговоримо про структуру даних, яка керує нашим життям набагато частіше, ніж ви думаєте. Від того, як ваш смартфон вирішує, яке повідомлення показати першим, до того, як лікарі в реанімації рятують життя.

Тема сьогоднішнього уроку — Priority Queues (Черги з пріоритетом).

1. 🔥 Вступ: Коли "хто перший — той і правий" не працює

Уявіть, що ви стоїте в черзі в касу супермаркету. Все чесно: хто прийшов раніше, того й обслуговують. Це класична черга FIFO (First In, First Out).

Але тепер уявіть відділення невідкладної допомоги в лікарні. Ви прийшли о 10:00 з легким кашлем. О 10:05 привозять пацієнта з серцевим нападом.

❓ Риторичне питання: Чи буде справедливо, якщо лікар скаже пацієнту з серцевим нападом: "Вибачте, станьте в кінець черги, цей хлопець з кашлем прийшов раніше"?

Звісно, ні! Тут порядок приходу не має значення. Має значення важливість (пріоритет).

Ось у чому проблема: Звичайні списки (Arrays) або черги (Queues) не вміють ефективно сортувати важливість на льоту. Якщо у вас мільйон завдань, і вам постійно треба витягувати "найважливіше", звичайний масив буде працювати надто повільно.

Нам потрібна структура, яка: 1. Приймає нові елементи (як звичайна черга). 2. Але коли ми просимо "дай наступного", вона віддає не того, хто найдовше чекав, а того, хто найважливіший.

2. 🧠 Теоретична база (Під капотом)

Отже, Priority Queue — це абстрактна ідея. Це "що" вона робить. А "як" вона це робить?

Найчастіше під капотом використовується структура, яка називається Купа (Heap).

🌳 Аналогія: Родинне дерево (піраміда)

Уявіть собі піраміду з чисел. * На самій верхівці (корінь) сидить "Бос" — елемент з найвищим пріоритетом (найбільше або найменше число). * Кожен "батько" в цій піраміді важливіший за своїх "дітей".

Це називається Binary Heap (Двійкова купа).

⚙️ Як це працює (логіка, а не синтаксис):

Додавання (Push): Новачок приходить у самий низ піраміди. Якщо він крутіший за свого батька, вони міняються місцями (bubble up). Він спливає вгору, поки не знайде своє місце.
Видалення (Pop): Ми забираємо тільки "Боса" (верхівку). На його місце ставимо останнього новачка знизу, і він починає тонути вниз (bubble down), міняючись місцями з дітьми, поки ієрархія не відновиться.

📌 Що треба запам'ятати (обов'язково):

У звичайному списку знайти мінімум/максимум — це довго (O(n) — треба перевірити всіх).
У черзі з пріоритетом (на базі Heap) це миттєво (O(1) — він завжди на горі).
А перебудувати чергу після видалення — дуже швидко (O(log n)).

Інтуїтивно: Це не повне сортування (яке займає багато часу). Це "ледаче" впорядкування. Ми знаємо точно тільки те, хто перший. Решта — в процесі.

3. 🧪 Приклади (Python)

Ми будемо використовувати модуль heapq у Python. За замовчуванням він працює як Min-Heap (найменше число — найвищий пріоритет). Це як гольф: менше очок — краще.

Рівень 1: Прості числа

import heapq

# Створюємо порожню купу
numbers = []

# Додаємо числа (у довільному порядку)
heapq.heappush(numbers, 10)
heapq.heappush(numbers, 1)
heapq.heappush(numbers, 5)

print(f"Внутрішній стан купи: {numbers}") 
# ❓ Питання до студента: Що ми побачимо? [1, 10, 5]? [1, 5, 10]?

Пояснення: Python не сортує весь список ідеально! Він гарантує, що numbers[0] (перший елемент) — найменший. Решта може виглядати хаотично, але це структура дерева в масиві.

А тепер дістаємо елементи:

first = heapq.heappop(numbers)
second = heapq.heappop(numbers)

print(f"Перший вийшов: {first}")   # Очікуємо: 1
print(f"Другий вийшов: {second}")  # Очікуємо: 5 (бо 5 < 10)

Рівень 2: Реальна задача (Планувальник завдань)

У реальному житті ми працюємо не просто з числами, а з об'єктами. Уявіть сервер, який обробляє задачі. Ми використовуємо кортеж (пріоритет, назва_задачі).

tasks = []

# 1 - найвищий пріоритет (критично), 100 - низький
heapq.heappush(tasks, (3, "Відправити email"))
heapq.heappush(tasks, (1, "Виправити критичний баг"))
heapq.heappush(tasks, (2, "Оновити іконку"))

print("Починаємо роботу:")

while tasks:
    priority, task_name = heapq.heappop(tasks)
    print(f"Виконую: {task_name} (Пріоритет: {priority})")

Результат: 1. Виправити критичний баг 2. Оновити іконку 3. Відправити email

Ми не сортували список вручну. Структура даних сама "виштовхнула" найважливіше наверх.

4. 🛠 Практична частина

Час забруднити руки кодом! Відкривайте IDE або блокнот.

🔹 Завдання 1: Розігрів

Скопіюйте приклад із задачами вище. Додайте туди задачу (0, "Врятувати сервер") вже після того, як додали інші, але перед запуском циклу while. Перевірте: Чи вийде ця задача першою? Чому?

🔹 Завдання 2: Змінюємо правила (Max-Heap)

Python реалізує Min-Heap (менше число = важливіше). Але що, якщо у вашій грі вищий рівень (Level 50) має пріоритет над нижчим (Level 1)? Завдання: Як використати heapq, щоб діставати найбільші числа першими, не переписуючи бібліотеку? (Підказка: математика. Що станеться, якщо множити пріоритет на -1?)

🔹 Завдання 3: Баг в системі

Ви пишете систему для посадки пасажирів у літак. passengers = [] Ви додаєте: ("Business", "Oleg"), ("Economy", "Anna"), ("First", "John"). Коли ви робите heappop, хто вийде першим? Чому це неправильно? Виправте код так, щоб пріоритет працював коректно (First > Business > Economy).

🔹 Завдання 4: Міні-кейс "Об'єднання списків"

У вас є 3 флешки з відсортованими файлами (за датою). list1 = [1, 4, 7], list2 = [2, 5, 8], list3 = [3, 6, 9]. Використайте heapq.merge (або просто купу), щоб злити їх в один ідеально відсортований потік. Це класичне питання на співбесіді в Google!

5. 💡 Мислення як у розробника

Як відрізнити новачка від профі в цій темі?

1. Помилка новачка: Використовувати звичайний список list.sort() кожного разу, коли додається новий елемент. Чому це погано: sort() — це повільно ($O(N \log N)$). Якщо ви робите це в циклі, ваша програма "зависне" на великих даних. heappush робить це миттєво ($O(\log N)$).

2. Пастка стабільності: Якщо два елементи мають однаковий пріоритет (наприклад, два пацієнти з пріоритетом 1), heapq почне порівнювати самі дані (імена пацієнтів). Якщо дані порівнювати не можна — програма впаде. Рішення профі: Зберігайте лічильник входу (entry_count). (пріоритет, номер_приходу, задача). Тоді при рівному пріоритеті виграє той, хто прийшов раніше.

3. Коли використовувати: * Pathfinding (Пошук шляху): Алгоритми GPS (Dijkstra, A) використовують це, щоб обирати найкоротшу дорогу. * Стиснення даних: Алгоритм Хаффмана (ZIP-архіви). * Планувальники OS:* Процесор вашого комп'ютера прямо зараз використовує цю чергу, щоб вирішити, якому вікну дати ресурси.

6. 🧩 Підсумок

Отже, що ми маємо в сухому залишку:

Priority Queue — це черга, де VIP-персони проходять без черги.
Це набагато швидше, ніж постійно сортувати масив.
У Python це реалізовано через модуль heapq (купа).
Ви тепер знаєте, як обробляти потоки даних, де є терміновість.

Що ви тепер вмієте: Ви можете написати скрипт, який обробляє тисячі подій і завжди знає, що найважливіше зробити прямо зараз, не витрачаючи час на перебирання всього списку.

🔮 Тизер наступного уроку:

Сьогодні ми говорили про "дерева" (купи) досить абстрактно. Але що, якщо нам потрібно не просто пріоритет, а зв'язки між містами на карті чи друзями у Facebook? На наступному уроці ми візьмемо нашу чергу з пріоритетом і засунемо її в Графи, щоб знайти найкоротший шлях до успіху.

Готові? Тоді до зустрічі! 💻🚀