Что такое двоичная куча и очередь с приоритетом?

Куча — полное двоичное дерево с правилом: значение в каждом узле не больше значений его потомков (для min-кучи; в max-куче наоборот). Это слабее порядка в дереве поиска — между братьями порядка нет, — зато поддерживать такое правило дешевле.

Хранение в массиве. Полное дерево ложится в массив без пропусков: корень — в позиции 0, потомки элемента i — в 2i+1 и 2i+2, родитель — в (i−1)//2. Ссылки не нужны.

Операции:

• посмотреть минимум — O(1), это корень;
• вставка — кладём элемент в конец и «поднимаем» (sift up), пока он меньше родителя: O(log n);
• извлечение минимума — ставим последний элемент в корень и «опускаем» (sift down), меняя с меньшим потомком: O(log n);
• построение кучи из массива — O(n), а не O(n log n), если просеивать снизу вверх.

Очередь с приоритетом — структура «положить с приоритетом, достать самый приоритетный». Её почти всегда реализуют кучей: heapq в Python, PriorityQueue в Java.

Применения: планировщики задач, алгоритм Дейкстры и A*, поиск k наибольших элементов (куча размера k — O(n log k)), слияние k отсортированных списков, медиана потока (две кучи), пирамидальная сортировка.

import heapq

def top_k(nums, k):
    heap = []                       # min-куча из k наибольших
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)     # выкидываем наименьший
    return sorted(heap, reverse=True)

top_k([5, 1, 9, 3, 7, 2], 3)        # [9, 7, 5]