Что такое Heap?

Heap (Куча)

Heap (куча) — это специальная структура данных, основанная на полном бинарном дереве, где каждый родитель имеет значение не больше (min-heap) или не меньше (max-heap) своих детей. Это позволяет эффективно находить минимальный или максимальный элемент за O(1), а вставлять и удалять за O(log n).

Два типа Heap

Min-Heap — родитель всегда меньше детей:

        1
       / \
      3   2
     / \
    7   4

Минимальный элемент всегда в корне (1).

Max-Heap — родитель всегда больше детей:

        10
        /  \
       5    9
      / \
     2   3

Максимальный элемент всегда в корне (10).

Heap в памяти

Heap представляется как список, где для элемента с индексом i:

• Левый потомок находится по индексу 2*i + 1
• Правый потомок находится по индексу 2*i + 2
• Родитель находится по индексу (i-1) // 2

Массив: [1, 3, 2, 7, 4]
Индекс: [0, 1, 2, 3, 4]

     1(0)
    /    \
  3(1)   2(2)
  /  \
7(3) 4(4)

Heap в Python

В Python есть встроенный модуль heapq для работы с min-heap:

import heapq

# Создание heap из списка
nums = [3, 1, 4, 1, 5, 9, 2, 6]
heap = nums.copy()
heapq.heapify(heap)  # Преобразуем в heap за O(n)
print(heap)  # [1, 1, 2, 3, 5, 9, 4, 6]

# Получение минимума
min_val = heap[0]  # O(1)
print(min_val)  # 1

# Извлечение минимума и добавление нового
min_val = heapq.heappop(heap)  # O(log n)
print(min_val)  # 1
heapq.heappush(heap, 0)  # O(log n)

Операции с Heap

import heapq

heap = []

# 1. Push — добавление элемента
heapq.heappush(heap, 5)   # O(log n)
heapq.heappush(heap, 2)
heapq.heappush(heap, 10)
heapq.heappush(heap, 1)
print(heap)  # [1, 2, 10, 5]

# 2. Pop — извлечение минимума
min_val = heapq.heappop(heap)  # O(log n)
print(min_val)  # 1
print(heap)  # [2, 5, 10]

# 3. PushPop — вставка и извлечение за один раз
val = heapq.heappushpop(heap, 3)  # O(log n)
print(val)  # 2
print(heap)  # [3, 5, 10]

# 4. Peek (посмотреть минимум без удаления)
min_val = heap[0]  # O(1)
print(min_val)  # 3

Max-Heap в Python

Поскольку в Python нет встроенного max-heap, используем трюк с отрицанием:

import heapq

heap = []

# Добавляем отрицательные значения
heapq.heappush(heap, -10)  # Добавляем 10 как max
heapq.heappush(heap, -5)
heapq.heappush(heap, -15)

# Извлекаем максимум
max_val = -heapq.heappop(heap)  # 15
print(max_val)  # 15

Или используйте кастомный класс:

import heapq
from functools import total_ordering

@total_ordering
class MaxHeapItem:
    def __init__(self, val):
        self.val = val
    
    def __lt__(self, other):
        return self.val > other.val  # Обратное сравнение
    
    def __eq__(self, other):
        return self.val == other.val

heap = []
heapq.heappush(heap, MaxHeapItem(10))
heapq.heappush(heap, MaxHeapItem(5))
max_val = heapq.heappop(heap).val  # 10

Практический пример: K наименьших элементов

import heapq

def k_smallest(arr, k):
    """Находит k наименьших элементов. O(n log k)"""
    return heapq.nsmallest(k, arr)

def k_largest(arr, k):
    """Находит k наибольших элементов. O(n log k)"""
    return heapq.nlargest(k, arr)

arr = [3, 1, 4, 1, 5, 9, 2, 6]
print(k_smallest(arr, 3))  # [1, 1, 2]
print(k_largest(arr, 3))   # [9, 6, 5]

Пример: Merge K отсортированных списков

import heapq

def merge_k_lists(lists):
    """Объединяет k отсортированных списков. O(n log k)"""
    heap = []
    
    # Добавляем первый элемент каждого списка с индексом списка
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    
    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        
        # Добавляем следующий элемент из того же списка
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
    
    return result

lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
print(merge_k_lists(lists))  # [1, 1, 2, 3, 4, 4, 5, 6]

Пример: Priority Queue (очередь с приоритетом)

import heapq
from dataclasses import dataclass

@dataclass
class Task:
    priority: int
    name: str
    
    def __lt__(self, other):
        return self.priority < other.priority

pq = []

heapq.heappush(pq, Task(3, "low"))
heapq.heappush(pq, Task(1, "high"))
heapq.heappush(pq, Task(2, "medium"))

while pq:
    task = heapq.heappop(pq)
    print(f"Processing: {task.name} (priority: {task.priority})")
    # Processing: high (priority: 1)
    # Processing: medium (priority: 2)
    # Processing: low (priority: 3)

Сложность операций

Когда использовать Heap

1. Priority Queue — очередь с приоритетом
2. K наименьших/наибольших элементов
3. Median Finder — эффективный поиск медианы
4. Dijkstra's Algorithm — кратчайший путь
5. Huffman Coding — оптимальное кодирование
6. Min-Cost Spanning Tree — задачи на графах

Heap это фундаментальная структура данных для оптимизации алгоритмов, где нужен быстрый доступ к минимальному или максимальному элементу.