Heap/Priority Queue — LeetCode на Python: Полный

Heap / Priority Queue

Куча для доступа к минимальному/максимальному элементу за O(1). Вставка и извлечение за O(log n).

#1. Суть паттерна

Heap (Куча) — это древовидная структура данных, удовлетворяющая свойству кучи: родитель больше (max-heap) или меньше (min-heap) детей. Priority Queue — абстрактный тип данных, часто реализуемый через кучу.

#1.1 Термины

Куча (Heap) — древовидная структура, где родитель больше (max-heap) или меньше (min-heap) детей.

Дерево отрезков (Segment Tree) — структура для диапазонных запросов и обновлений.

Префиксное дерево (Trie) — дерево для хранения строк, где каждый узел представляет префикс.

Система непересекающихся множеств (DSU/Union-Find) — структура для эффективного объединения множеств и проверки принадлежности.

#Когда применять

✅ K-й наибольший/наименьший — найти k-й элемент по порядку
✅ Top K элементов — k наибольших/наименьших частот
✅ Слияние отсортированных списков — merge k sorted lists
✅ Медиана потока — find median from data stream
✅ Жадные алгоритмы — задачи с приоритетами
✅ Планирование задач — task scheduler

#Предусловия

Частичный порядок — нужен только мин/макс, не полная сортировка
Динамические данные — элементы добавляются/удаляются
Приоритетная обработка — элементы с большим приоритетом обрабатываются первыми

#Типы куч

Тип	Свойство	Корень	Применение
Min-heap	parent ≤ children	Минимум	K largest, merge lists
Max-heap	parent ≥ children	Максимум	K smallest
Custom heap	по ключу	По ключу	Top K frequent

#Структура кучи

Min-heap: [1, 3, 2, 7, 6, 4, 5]

Дерево:
        1
       / \
      3   2
     / \ / \
    7  6 4  5

Массив (0-based):
index: 0  1  2  3  4  5  6
value: 1  3  2  7  6  4  5

parent(i) = (i - 1) // 2
left(i) = 2*i + 1
right(i) = 2*i + 2

#Сравнение с альтернативами

Задача	Heap	Sorted List	BST	Linear Scan
Найти минимум	✅ O(1)	✅ O(1)	✅ O(log n)	❌ O(n)
Вставка	✅ O(log n)	❌ O(n)	✅ O(log n)	✅ O(1)
Удаление минимума	✅ O(log n)	❌ O(n)	✅ O(log n)	❌ O(n)
K-й наибольший	✅ O(n log k)	⚠️ O(n log n)	⚠️ O(n log n)	❌ O(n²)
Медиана потока	✅ O(log n)	❌ O(n)	⚠️ O(log n)	❌ O(n)

Вывод: Heap оптимален для задач с динамическим поиском мин/макс и K-й элемент.

#Python heapq

import heapq

# Min-heap
heap = []
heapq.heappush(heap, value)      # O(log n)
min_val = heapq.heappop(heap)    # O(log n)
min_val = heap[0]                # O(1) - peek

# Max-heap (через отрицание)
heapq.heappush(heap, -value)
max_val = -heapq.heappop(heap)

# K largest/smallest
heapq.nlargest(k, iterable, key=...)
heapq.nsmallest(k, iterable, key=...)

# Heapify
heapq.heapify(list)              # O(n)

#2. Шаблон

import heapq

# Min-heap
heap = []
heapq.heappush(heap, value)
min_val = heapq.heappop(heap)
min_val = heap[0]  # Peek

# Max-heap (через отрицание)
heapq.heappush(heap, -value)
max_val = -heapq.heappop(heap)

# K largest
heapq.nlargest(k, iterable)
heapq.nsmallest(k, iterable)

# Построение кучи из списка
heapq.heapify(list)  # O(n)

# Замена минимального
heapq.heapreplace(heap, item)  # pop + push

#3. Разбор задач

#Задача 1: Kth Largest Element (LeetCode 215) 🟦 Medium

Ссылка: https://leetcode.com/problems/kth-largest-element-in-an-array/

Условие: Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в отсортированном порядке.

Примеры:

Ввод: nums = [3,2,1,5,6,4], k = 2
Вывод: 5

Ввод: nums = [3,2,3,1,2,4,5,5,6], k = 4
Вывод: 4

Ограничения:

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

💡 Подсказка: Используйте min-heap размера k. Добавляйте все элементы, при превышении размера удаляйте минимальный. В конце heap[0] — k-й наибольший.

#Визуализация

Вставляем 0 в min-heap [1, 3, 2, 7, 6, 4, 5]:

Шаг 1: Добавляем в конец
        1
       / \
      3   2
     / \ / \
    7  6 4  5
   /
  0 ← новый элемент

Шаг 2: 0 < 3, меняем местами (swap up)
        1
       / \
      0   2
     / \ / \
    7  6 4  5
   /
  3

Шаг 3: 0 < 1, меняем местами
        0 ← новый корень
       / \
      1   2
     / \ / \
    7  6 4  5
   /
  3

Результат: [0, 1, 2, 7, 6, 4, 5, 3]

Решение:

import heapq

def findKthLargest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

# Или через nlargest
def findKthLargest(nums, k):
    return heapq.nlargest(k, nums)[-1]

Объяснение:

Min-heap размера k хранит k наибольших элементов
Минимальный из них (heap[0]) — k-й наибольший в общем
heapq.nlargest(k, nums)[-1] — более простая версия

Сложность:

Время: O(n log k)
Память: O(k)

#Задача 2: Top K Frequent Elements (LeetCode 347) 🟦 Medium

Ссылка: https://leetcode.com/problems/top-k-frequent-elements/

Условие: Дан целочисленный массив nums и целое число k. Верните k наиболее частых элементов.

Примеры:

Ввод: nums = [1,1,1,2,2,3], k = 2
Вывод: [1,2]

Ввод: nums = [1], k = 1
Вывод: [1]

Ограничения:

1 <= nums.length <= 10⁵
k в диапазоне [1, количество уникальных элементов]

💡 Подсказка: Используйте Counter для подсчёта частот. heapq.nlargest(k, keys, key=count.get) вернёт k элементов с наибольшей частотой.

Решение:

import heapq
from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

Объяснение:

Counter(nums) — словарь {элемент: частота}
heapq.nlargest(k, count.keys(), key=count.get) — k элементов с наибольшей частотой
key=count.get использует частоту для сравнения

Сложность:

Время: O(n + m log k), где m — количество уникальных элементов
Память: O(m)

#Задача 3: Merge K Sorted Lists (LeetCode 23) 🔴 Hard

Ссылка: https://leetcode.com/problems/merge-k-sorted-lists/

Условие: Дан массив отсортированных связных списков. Объедините их в один отсортированный список.

Примеры:

Ввод: lists = [[1,4,5],[1,3,4],[2,6]]
Вывод: [1,1,2,3,4,4,5,6]

Ввод: lists = []
Вывод: []

Ввод: lists = [[]]
Вывод: []

Ограничения:

0 <= lists.length <= 10⁴
0 <= lists[i].length <= 500
-10⁴ <= lists[i][j] <= 10⁴

💡 Подсказка: Используйте min-heap кортежей (val, index). heapq сравнивает по первому элементу кортежа.

Решение:

import heapq

def mergeKLists(lists):
    heap = []
    # Добавляем первый элемент каждого списка
    for i, l in enumerate(lists):
        if l:
            heapq.heappush(heap, (l.val, i))

    dummy = ListNode(0)
    current = dummy

    while heap:
        val, i = heapq.heappop(heap)
        current.next = lists[i]
        current = current.next

        # Добавляем следующий элемент из того же списка
        if lists[i].next:
            lists[i] = lists[i].next
            heapq.heappush(heap, (lists[i].val, i))

    return dummy.next

Объяснение:

heap хранит (val, index) — значение и индекс списка
heapq сравнивает кортежи лексикографически (по val первым)
После извлечения добавляем следующий элемент из того же списка

Сложность:

Время: O(n log k), где n — общее количество элементов, k — количество списков
Память: O(k)

#Задача 4: Find Median from Data Stream (LeetCode 295) 🔴 Hard

Ссылка: https://leetcode.com/problems/find-median-from-data-stream/

Условие: Реализуйте структуру данных MedianFinder:

void addNum(int num) — добавляет число
double findMedian() — возвращает медиану всех добавленных чисел

Примеры:

Ввод: ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
      [[], [1], [2], [], [3], []]
Вывод: [null, null, null, 1.5, null, 2.0]
Объяснение:
  addNum(1) → [1]
  addNum(2) → [1, 2]
  findMedian() → (1+2)/2 = 1.5
  addNum(3) → [1, 2, 3]
  findMedian() → 2

Ограничения:

-10⁵ <= num <= 10⁵
До 5 × 10⁴ вызовов addNum и findMedian

💡 Подсказка: Используйте два heap: max-heap для левой половины (small) и min-heap для правой (large). Балансируйте размеры.

#Визуализация

Извлекаем минимум из [0, 1, 2, 7, 6, 4, 5, 3]:

Шаг 1: Заменяем корень на последний элемент
        3 ← последний стал корнём
       / \
      1   2
     / \ / \
    7  6 4  5

Шаг 2: 3 > 1, меняем местами (swap down)
        1
       / \
      3   2
     / \ / \
    7  6 4  5

Шаг 3: 3 > 2, меняем местами
        1
       / \
      2   3
     / \ / \
    7  6 4  5

Результат: [1, 2, 3, 7, 6, 4, 5], извлечён 0

Решение:

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max-heap (левая половина)
        self.large = []  # min-heap (правая половина)

    def addNum(self, num):
        # Добавляем в large, затем переносим минимальный в small
        heapq.heappush(self.small, -heapq.heappushpop(self.large, num))

        # Балансируем: large может быть на 1 больше
        if len(self.large) < len(self.small):
            heapq.heappush(self.large, -heapq.heappop(self.small))

    def findMedian(self):
        if len(self.large) > len(self.small):
            return self.large[0]
        return (self.large[0] - self.small[0]) / 2

Объяснение:

small — max-heap (храним отрицательные значения)
large — min-heap
large может быть на 1 элемент больше small
Медиана: если размеры равны — среднее, иначе — large[0]

Сложность:

Время: addNum O(log n), findMedian O(1)
Память: O(n)

#Задача 5: Task Scheduler (LeetCode 621) 🟦 Medium

Ссылка: https://leetcode.com/problems/task-scheduler/

Условие: Дан массив задач tasks (буквы A-Z) и целое n — период охлаждения. Между двумя одинаковыми задачами должно пройти минимум n интервалов.

Верните минимальное количество интервалов для выполнения всех задач.

Примеры:

Ввод: tasks = ["A","A","A","B","B","B"], n = 2
Вывод: 8
Объяснение: A → B → idle → A → B → idle → A → B

Ввод: tasks = ["A","A","A","B","B","B"], n = 0
Вывод: 6

Ввод: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Вывод: 16

Ограничения:

1 <= tasks.length <= 10⁴
tasks[i] — заглавная английская буква
0 <= n <= 100

💡 Подсказка: Используйте max-heap частот. Каждый цикл: берём до n+1 задач из heap. Если heap не пуст — время += n+1, иначе += количество взятых.

Решение:

import heapq
from collections import Counter

def leastInterval(tasks, n):
    count = Counter(tasks)
    heap = [-c for c in count.values()]  # Max-heap через отрицание
    heapq.heapify(heap)

    time = 0
    while heap:
        i, temp = 0, []
        # Берём до n+1 задач
        while i <= n and heap:
            temp.append(heapq.heappop(heap) + 1)  # +1 т.к. отрицательное
            i += 1

        # Возвращаем задачи с оставшимися выполнениями
        for t in temp:
            if t < 0:
                heapq.heappush(heap, t)

        # Время: n+1 если есть ещё задачи, иначе i
        time += n + 1 if heap else i

    return time

Объяснение:

heap хранит отрицательные частоты (max-heap)
Каждый цикл: берём до n+1 различных задач
Если heap не пуст — ждём n+1 интервалов (включая idle)
Если heap пуст — время += количество фактически взятых задач

Сложность:

Время: O(n × m), где m — количество уникальных задач
Память: O(m)

#Задача 6: K Closest Points to Origin (LeetCode 973) 🟦 Medium

Ссылка: https://leetcode.com/problems/k-closest-points-to-origin/

Условие: Дан массив точек points на плоскости и целое k. Верните k ближайших к началу координат (0, 0) точек.

Примеры:

Ввод: points = [[1,3],[-2,2]], k = 1
Вывод: [[-2,2]]
Объяснение: 1²+3²=10, (-2)²+2²=8 → вторая ближе

Ввод: points = [[3,3],[5,-1],[-2,4]], k = 2
Вывод: [[3,3],[-2,4]] или [[-2,4],[3,3]]

Ограничения:

1 <= k <= points.length <= 10⁴
-10⁴ <= points[i][j] <= 10⁴

💡 Подсказка: Используйте heapq.nsmallest(k, points, key=lambda p: p[0]² + p[1]²). Квадрат расстояния достаточно для сравнения.

Решение:

import heapq

def kClosest(points, k):
    return heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2)

Объяснение:

Квадрат евклидова расстояния: x² + y²
Квадратный корень не нужен для сравнения
heapq.nsmallest вернёт k точек с наименьшим расстоянием

Сложность:

Время: O(n log k)
Память: O(k)

#Задача 7: Reorganize String (LeetCode 767) 🟦 Medium

Ссылка: https://leetcode.com/problems/reorganize-string/

Условие: Дана строка s. Переставьте символы так, чтобы никакие два одинаковых символа не были соседними.

Верните любую допустимую перестановку или пустую строку, если невозможно.

Примеры:

Ввод: s = "aab"
Вывод: "aba"

Ввод: s = "aaab"
Вывод: ""

Ввод: s = "vvvlo"
Вывод: "vlvov"

Ограничения:

1 <= s.length <= 500
s из строчных английских букв

💡 Подсказка: Используйте max-heap частот. Берём 2 наиболее частых символа, добавляем в результат, возвращаем в heap если остались.

Решение:

import heapq
from collections import Counter

def reorganizeString(s):
    count = Counter(s)
    heap = [(-c, char) for char, c in count.items()]
    heapq.heapify(heap)

    result = []
    while len(heap) >= 2:
        c1, char1 = heapq.heappop(heap)
        c2, char2 = heapq.heappop(heap)
        result.extend([char1, char2])

        if c1 + 1 < 0:
            heapq.heappush(heap, (c1 + 1, char1))
        if c2 + 1 < 0:
            heapq.heappush(heap, (c2 + 1, char2))

    if heap:
        c, char = heap[0]
        if -c > 1:
            return ''  # Невозможно
        result.append(char)

    return ''.join(result)

Объяснение:

heap хранит (-частота, символ) — max-heap
Берём 2 наиболее частых символа, добавляем в результат
Возвращаем в heap если остались (частота > 1)
Если остался один символ с частотой > 1 — невозможно

Сложность:

Время: O(n log m), где m — количество уникальных символов
Память: O(m)

#Задача 8: Ugly Number II (LeetCode 264) 🟦 Medium

Ссылка: https://leetcode.com/problems/ugly-number-ii/

Условие: Ugly number — положительное число, простые делители которого только 2, 3, 5.

Дано целое n. Верните n-е ugly number.

Примеры:

Ввод: n = 10
Вывод: 12
Объяснение: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]

Ввод: n = 1
Вывод: 1

Ограничения:

1 <= n <= 1690

💡 Подсказка: Используйте min-heap и set для уникальности. Извлекаем минимальный, умножаем на 2, 3, 5, добавляем обратно.

Решение:

import heapq

def nthUglyNumber(n):
    heap = [1]
    seen = {1}
    primes = [2, 3, 5]

    for _ in range(n):
        ugly = heapq.heappop(heap)
        for p in primes:
            new_ugly = ugly * p
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(heap, new_ugly)

    return ugly

Объяснение:

heap хранит ugly numbers в порядке возрастания
seen предотвращает дубликаты (например, 6 = 2×3 = 3×2)
Извлекаем минимальный n раз
Умножаем на 2, 3, 5, добавляем новые

Сложность:

Время: O(n log n)
Память: O(n)

#4. Шпаргалка

Задача	Ключевая идея
Kth Largest	Min-heap размера k
Top K Frequent	Counter + nlargest
Merge K Lists	Heap кортежей (val, index)
Find Median	Два heap (max + min)
Task Scheduler	Max-heap частот, цикл n+1
K Closest	nsmallest с ключом расстояния
Reorganize String	Pop 2, push back
Ugly Number	Heap + set для уникальности

#6. ⚠️ Common Mistakes

#❌ Ошибка 1: Попытка использовать max-heap напрямую

Проблема: Python heapq поддерживает только min-heap.

# ❌ Неправильно — heapq не поддерживает max-heap
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 10)
max_val = heapq.heappop(heap)  # Вернёт 5 (минимум), а не 10!

# ✅ Правильно — используем отрицание
heap = []
heapq.heappush(heap, -5)
heapq.heappush(heap, -10)
max_val = -heapq.heappop(heap)  # Вернёт 10

Почему это неправильно: heapq всегда возвращает минимум.

Как исправить: Используйте отрицательные значения для max-heap.

#❌ Ошибка 2: Изменение элементов в куче

Проблема: Прямое изменение элементов нарушает свойство кучи.

# ❌ Неправильно — прямое изменение
heap[0] = new_value  # Нарушает свойство кучи!

# ✅ Правильно — использовать heapreplace
heapq.heapreplace(heap, new_value)  # Удаляет мин, добавляет new_value

Почему это неправильно: Свойство кучи нарушается, дальнейшие операции неверны.

#❌ Ошибка 3: Неправильное использование кортежей

Проблема: heapq сравнивает кортежи лексикографически.

# ❌ Неправильно — если val одинаковы, сравнивается второй элемент
heapq.heappush(heap, (val, object))  # Ошибка если object не сравним!

# ✅ Правильно — используем уникальный id
heapq.heappush(heap, (val, i, object))  # i — уникальный индекс

Почему это неправильно: При одинаковых val heapq попытается сравнить второй элемент.

#❌ Ошибка 4: Ожидание полной сортировки

Проблема: Куча не гарантирует полный порядок элементов.

# ❌ Неправильно — ожидаем отсортированный список
heap = [1, 3, 2, 7, 6, 4, 5]
# heap[1] может быть больше heap[2] — это нормально!

# ✅ Правильно — гарантирован только минимум
min_val = heap[0]  # Всегда минимум

Почему это неправильно: Куча гарантирует только parent ≤ children.

#❌ Ошибка 5: Забыли heapify после создания списка

Проблема: Список не является кучей без heapify.

# ❌ Неправильно — просто список
heap = [5, 3, 8, 1, 9]
min_val = heap[0]  # 5, но минимум = 1!

# ✅ Правильно — heapify
heap = [5, 3, 8, 1, 9]
heapq.heapify(heap)  # O(n)
min_val = heap[0]  # 1 ✓

Почему это неправильно: Список не является кучей без вызова heapify.

#7. 🎯 Попробуйте сами

#Задача для самостоятельного решения

Условие: Дан поток целых чисел. Найдите медиану после добавления каждого нового числа.

Пример:

Ввод: [1, 2, 3, 4, 5]
Вывод: [1, 1.5, 2, 2.5, 3]
Объяснение:
[1] → медиана = 1
[1,2] → медиана = (1+2)/2 = 1.5
[1,2,3] → медиана = 2
[1,2,3,4] → медиана = (2+3)/2 = 2.5
[1,2,3,4,5] → медиана = 3

💡 Подсказка 1

Используйте две кучи: max-heap для левой половины и min-heap для правой

💡 Подсказка 2

Балансируйте кучи так, чтобы их размеры отличались не более чем на 1

💡 Подсказка 3

Python heapq — только min-heap, используйте отрицание для max-heap

✅ Решение

import heapq

class MedianFinder:
    def __init__(self):
        self.max_heap = []  # Левая половина (отрицательные значения)
        self.min_heap = []  # Правая половина
    
    def addNum(self, num):
        # Добавляем в левую половину (max-heap через отрицание)
        heapq.heappush(self.max_heap, -num)
        
        # Балансируем: максимум левой должен быть <= минимума правой
        if (self.min_heap and -self.max_heap[0] > self.min_heap[0]):
            val = -heapq.heappop(self.max_heap)
            heapq.heappush(self.min_heap, val)
        
        # Балансируем размеры
        if len(self.max_heap) > len(self.min_heap) + 1:
            val = -heapq.heappop(self.max_heap)
            heapq.heappush(self.min_heap, val)
        elif len(self.min_heap) > len(self.max_heap):
            val = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -val)
    
    def findMedian(self):
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        return (-self.max_heap[0] + self.min_heap[0]) / 2

# Использование:
finder = MedianFinder()
result = []
for num in [1, 2, 3, 4, 5]:
    finder.addNum(num)
    result.append(finder.findMedian())
# result = [1, 1.5, 2, 2.5, 3]

Объяснение:

max_heap хранит левую половину (меньшие значения)
min_heap хранит правую половину (большие значения)
Медиана = максимум левой (если нечётное количество) или среднее двух средних
Балансируем так, чтобы len(max_heap) >= len(min_heap)

Сложность:

Время: O(log n) на добавление
Память: O(n)

#8. Заключение

Тип

Свойство

Корень

Применение

Min-heap

parent ≤ children

Минимум

K largest, merge lists

Max-heap

parent ≥ children

Максимум

K smallest

Custom heap

по ключу

По ключу

Top K frequent

Min-heap: [1, 3, 2, 7, 6, 4, 5] Дерево: 1 / \ 3 2 / \ / \ 7 6 4 5 Массив (0-based): index: 0 1 2 3 4 5 6 value: 1 3 2 7 6 4 5 parent(i) = (i - 1) // 2 left(i) = 2*i + 1 right(i) = 2*i + 2

Задача

Heap

Sorted List

BST

Linear Scan

Найти минимум

✅ O(1)

✅ O(log n)

❌ O(n)

Вставка

✅ O(log n)

❌ O(n)

✅ O(log n)

✅ O(1)

Удаление минимума

✅ O(log n)

❌ O(n)

✅ O(log n)

❌ O(n)

K-й наибольший

✅ O(n log k)

⚠️ O(n log n)

❌ O(n²)

Медиана потока

✅ O(log n)

❌ O(n)

⚠️ O(log n)

❌ O(n)

Вставляем 0 в min-heap [1, 3, 2, 7, 6, 4, 5]: Шаг 1: Добавляем в конец 1 / \ 3 2 / \ / \ 7 6 4 5 / 0 ← новый элемент Шаг 2: 0 < 3, меняем местами (swap up) 1 / \ 0 2 / \ / \ 7 6 4 5 / 3 Шаг 3: 0 < 1, меняем местами 0 ← новый корень / \ 1 2 / \ / \ 7 6 4 5 / 3 Результат: [0, 1, 2, 7, 6, 4, 5, 3]

Ввод: ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Вывод: [null, null, null, 1.5, null, 2.0] Объяснение: addNum(1) → [1] addNum(2) → [1, 2] findMedian() → (1+2)/2 = 1.5 addNum(3) → [1, 2, 3] findMedian() → 2

Извлекаем минимум из [0, 1, 2, 7, 6, 4, 5, 3]: Шаг 1: Заменяем корень на последний элемент 3 ← последний стал корнём / \ 1 2 / \ / \ 7 6 4 5 Шаг 2: 3 > 1, меняем местами (swap down) 1 / \ 3 2 / \ / \ 7 6 4 5 Шаг 3: 3 > 2, меняем местами 1 / \ 2 3 / \ / \ 7 6 4 5 Результат: [1, 2, 3, 7, 6, 4, 5], извлечён 0

Ввод: tasks = ["A","A","A","B","B","B"], n = 2 Вывод: 8 Объяснение: A → B → idle → A → B → idle → A → B Ввод: tasks = ["A","A","A","B","B","B"], n = 0 Вывод: 6 Ввод: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2 Вывод: 16

Ввод: points = [[1,3],[-2,2]], k = 1 Вывод: [[-2,2]] Объяснение: 1²+3²=10, (-2)²+2²=8 → вторая ближе Ввод: points = [[3,3],[5,-1],[-2,4]], k = 2 Вывод: [[3,3],[-2,4]] или [[-2,4],[3,3]]

Задача

Ключевая идея

Kth Largest

Min-heap размера k

Top K Frequent

Counter + nlargest

Merge K Lists

Heap кортежей (val, index)

Find Median

Два heap (max + min)

Task Scheduler

Max-heap частот, цикл n+1

K Closest

nsmallest с ключом расстояния

Reorganize String

Pop 2, push back

Ugly Number

Heap + set для уникальности

Ввод: [1, 2, 3, 4, 5] Вывод: [1, 1.5, 2, 2.5, 3] Объяснение: [1] → медиана = 1 [1,2] → медиана = (1+2)/2 = 1.5 [1,2,3] → медиана = 2 [1,2,3,4] → медиана = (2+3)/2 = 2.5 [1,2,3,4,5] → медиана = 3