Построение кучи, добавление и извлечение с нуля
Реализуйте просеивание вверх для добавления и просеивание вниз для извлечения, а затем постройте кучу из неотсортированного массива за O(n) с помощью алгоритма Флойда
«Построение кучи, добавление и извлечение с нуля» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Создание класса MinHeap
Реализация кучи с нуля демонстрирует понимание её внутренней механики и иногда встречается на собеседованиях для опытных разработчиков. Класс MinHeap оборачивает массив и предоставляет операции push, pop, peek и size. Внутри он поддерживает свойство кучи, вызывая просеивание вверх после push и просеивание вниз после pop. Понимание этой реализации делает работу модуля Python heapq полностью прозрачной.
class MinHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
self._sift_up(len(self._data) - 1)
def pop(self):
if len(self._data) == 1:
return self._data.pop()
min_val = self._data[0]
self._data[0] = self._data.pop() # move last to root
self._sift_down(0)
return min_val
def peek(self):
return self._data[0] if self._data else None
def size(self):
return len(self._data)
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
print('MinHeap class skeleton defined')Реализация просеивания вверх
Просеивание вверх сравнивает узел с его родителем и меняет их местами, поднимая узел вверх, пока нарушено свойство кучи (parent <= child для min-heap). Важно, что вставленный элемент находится в конце и поднимается на правильную позицию. Цикл while выполняется не более floor(log n) раз — это высота дерева. На каждом шаге присваивайте i = parent, чтобы продолжить движение вверх.
class MinHeap:
def __init__(self):
self._data = []
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
def _sift_up(self, i):
while i > 0:
p = self._parent(i)
if self._data[p] > self._data[i]: # parent > child: swap
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else:
break # heap property satisfied
def push(self, val):
self._data.append(val)
self._sift_up(len(self._data) - 1)
h = MinHeap()
for v in [5, 3, 8, 1, 4]:
h.push(v)
print(h._data) # valid min-heapРеализация просеивания вниз
Просеивание вниз перемещает узел вниз, многократно меняя его местами с наименьшим потомком (для min-heap), пока ни один потомок не окажется меньше него или узел не достигнет листа. Всегда сравнивайте узел с обоими потомками и меняйте его местами с меньшим из них, чтобы сохранить свойство кучи. Не забудьте проверить, что индексы потомков находятся в допустимых границах, прежде чем сравнивать значения.
def _sift_down(data, i):
n = len(data)
while True:
smallest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and data[l] < data[smallest]:
smallest = l
if r < n and data[r] < data[smallest]:
smallest = r
if smallest == i:
break # already the smallest among i, l, r
data[i], data[smallest] = data[smallest], data[i]
i = smallest
# Test: put a large value at root and sift down
heap = [10, 1, 2, 3, 4, 5, 6]
print('Before sift-down:', heap)
_sift_down(heap, 0)
print('After sift-down:', heap) # 1 should reach top, 10 sinkЗавершение реализации MinHeap с операцией Pop
Операция pop удаляет и возвращает корень (минимум для min-heap). Чтобы сохранить форму полного двоичного дерева, переместите последний элемент на место корня, а затем выполните просеивание вниз. Это не создаёт пропусков в массиве и сохраняет корректность представления. Особый случай: если остался только один элемент, извлеките и верните его напрямую, не выполняя просеивание вниз.
class MinHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
i = len(self._data) - 1
while i > 0:
p = (i - 1) // 2
if self._data[p] > self._data[i]:
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else: break
def pop(self):
if not self._data: return None
if len(self._data) == 1: return self._data.pop()
result = self._data[0]
self._data[0] = self._data.pop() # last -> root
i, n = 0, len(self._data)
while True:
s, l, r = i, 2*i+1, 2*i+2
if l < n and self._data[l] < self._data[s]: s = l
if r < n and self._data[r] < self._data[s]: s = r
if s == i: break
self._data[i], self._data[s] = self._data[s], self._data[i]
i = s
return result
h = MinHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)]) # [1,2,3,4,5,8] sortedАлгоритм построения кучи Флойда
Алгоритм Флойда строит min-heap из неотсортированного массива за O(n), вызывая просеивание вниз для каждого внутреннего узла, начиная с последнего внутреннего узла (n//2 - 1) и двигаясь к корню. Листья уже являются корректными одноэлементными кучами. Сложность O(n) объясняется тем, что большинство узлов находятся у основания дерева и должны просеиваться лишь на небольшое расстояние.
def heapify(arr):
n = len(arr)
# Start from last non-leaf: index n//2 - 1
# Work backward to root (index 0)
for i in range(n // 2 - 1, -1, -1):
# Sift down node at index i
j = i
while True:
s = j
l, r = 2*j+1, 2*j+2
if l < n and arr[l] < arr[s]: s = l
if r < n and arr[r] < arr[s]: s = r
if s == j: break
arr[j], arr[s] = arr[s], arr[j]
j = s
return arr
arr = [9, 7, 5, 3, 1, 8, 2, 4, 6]
print('Before:', arr)
heapify(arr)
print('After (min-heap):', arr) # arr[0] should be 1Почему алгоритм Флойда работает за O(n)
Доказательство сложности O(n): на высоте k в дереве находится n/2^(k+1) узлов. Каждый узел на высоте k выполняет не более k обменов во время просеивания вниз. Общая трудоёмкость = сумма по всем высотам k: n/2^(k+1) * k. Этот геометрический ряд сходится к O(n). Для сравнения, при наивной последовательной вставке каждый push выполняется за O(log n), поэтому n вставок требуют O(n log n). Алгоритм Флойда строго эффективнее для пакетного построения.
import time
import random
# Compare: O(n) heapify vs O(n log n) one-by-one
n = 100000
data = list(range(n, 0, -1)) # reverse sorted = worst case for push
# Method 1: Floyd's O(n)
data1 = data[:]
start = time.time()
for i in range(n // 2 - 1, -1, -1):
j = i
while True:
s = j; l, r = 2*j+1, 2*j+2
if l < n and data1[l] < data1[s]: s = l
if r < n and data1[r] < data1[s]: s = r
if s == j: break
data1[j], data1[s] = data1[s], data1[j]; j = s
print(f'Floyd heapify: {time.time()-start:.4f}s')
# Method 2: One-by-one insertion
import heapq
start = time.time()
heap = []
for x in data: heapq.heappush(heap, x)
print(f'Push one-by-one: {time.time()-start:.4f}s')Добавление элемента в существующую коллекцию кучи
heapq.heappushpop и heapq.heapreplace в Python — это эффективные объединённые операции. heappushpop(heap, item) добавляет новый элемент и сразу извлекает наименьший — это эффективнее двух отдельных вызовов. heapreplace(heap, item) за один проход извлекает наименьший элемент и добавляет новый (для корректной работы новый элемент должен быть >= старого минимума). Эти операции полезны в потоковых алгоритмах поиска k лучших элементов.
import heapq
heap = [1, 3, 5, 7, 9]
heapq.heapify(heap)
# heappushpop: push 2, then pop minimum
# More efficient than push + pop separately
result = heapq.heappushpop(heap, 2)
print('heappushpop(2):', result, '| heap:', heap)
# heapreplace: pop minimum, then push new item
# New item does NOT need to be larger (different from heappushpop)
result2 = heapq.heapreplace(heap, 4)
print('heapreplace(4):', result2, '| heap:', heap)
# Use case: maintaining a fixed-size top-k heap
# heappushpop is the standard patternРеализация MaxHeap с нуля
MaxHeap меняет направление сравнения: родитель должен быть больше или равен всем потомкам. Просто инвертируйте сравнение в просеивании вверх и просеивании вниз. Другой вариант — обернуть значения в класс с инвертированным знаком или менять знаки целых чисел, как это делается с heapq в Python. Реализация с нуля показывает, что min-heap и max-heap имеют одинаковую структуру, а различаются только оператором сравнения.
class MaxHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
i = len(self._data) - 1
while i > 0:
p = (i - 1) // 2
if self._data[p] < self._data[i]: # FLIP: parent < child = violation
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else: break
def pop(self):
if not self._data: return None
if len(self._data) == 1: return self._data.pop()
result = self._data[0]
self._data[0] = self._data.pop()
i, n = 0, len(self._data)
while True:
g = i; l, r = 2*i+1, 2*i+2
if l < n and self._data[l] > self._data[g]: g = l # FLIP
if r < n and self._data[r] > self._data[g]: g = r # FLIP
if g == i: break
self._data[i], self._data[g] = self._data[g], self._data[i]; i = g
return result
h = MaxHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)]) # [8,5,4,3,2,1]Удаление произвольного элемента из кучи
Удаление произвольного элемента (не корня) из кучи выполняется за O(log n), но требует знания индекса элемента. Замените этот элемент последним, удалите последний элемент, а затем выполните для замены просеивание вверх или вниз (нарушить свойство кучи может только одно из этих направлений). Этот приём используется в алгоритме Дейкстры с ленивым удалением и в очередях с приоритетом, поддерживающих операции уменьшения ключа.
def delete_at_index(heap, i):
n = len(heap)
heap[i] = heap[n - 1]
heap.pop()
if i >= len(heap):
return # deleted the last element
# Try sift-up first
p = (i - 1) // 2
if i > 0 and heap[i] < heap[p]:
while i > 0:
p = (i - 1) // 2
if heap[p] > heap[i]:
heap[p], heap[i] = heap[i], heap[p]; i = p
else: break
else: # sift down
j = i; n2 = len(heap)
while True:
s = j; l, r = 2*j+1, 2*j+2
if l < n2 and heap[l] < heap[s]: s = l
if r < n2 and heap[r] < heap[s]: s = r
if s == j: break
heap[j], heap[s] = heap[s], heap[j]; j = s
heap = [1, 3, 2, 7, 4, 5, 6]
print('Before:', heap)
delete_at_index(heap, 2) # delete element at index 2 (value=2)
print('After:', heap) # 2 removed, heap still validКуча в задаче о k наиболее часто встречающихся элементах
Наиболее часто встречающиеся элементы (LeetCode №347) использует min-heap размера k. Поддерживайте min-heap, где каждая запись имеет вид (frequency, element). Обрабатывайте каждый уникальный элемент: если в куче меньше k элементов, добавьте его; в противном случае, если частота нового элемента превышает минимум в куче, извлеките минимум и добавьте новый элемент. В результате куча содержит k наиболее часто встречающихся элементов, а общая сложность составляет O(n log k).
import heapq
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums)
# Min-heap of (frequency, num)
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap) # remove least frequent
return [num for freq, num in heap]
print(top_k_frequent([1,1,1,2,2,3], 2)) # [1, 2]
print(top_k_frequent([4,4,4,3,3,2,1], 2)) # [4, 3]Применение куч в планировании
Помимо соревновательного программирования, кучи лежат в основе реальных систем планирования. Планировщики задач операционных систем используют очередь с приоритетом (кучу), чтобы всегда запускать готовый процесс с наивысшим приоритетом. В моделировании, управляемом событиями, события обрабатываются в порядке времени с помощью мин-кучи, упорядоченной по времени события. Планировщики сетевых пакетов расставляют приоритеты трафика по классу качества обслуживания. Понимание кучи даёт Вам мысленную модель всех этих систем и естественно возникает на собеседованиях по проектированию систем, где обсуждаются очереди и планирование.
import heapq
# Simple event-driven simulation using a heap
events = [] # (time, event_description)
def schedule(time, event):
heapq.heappush(events, (time, event))
def process_next():
time, event = heapq.heappop(events)
print(f't={time}: {event}')
return time, event
# Schedule events out of order:
schedule(10, 'Send email')
schedule(3, 'Open app')
schedule(7, 'Process request')
schedule(1, 'Start server')
# Process in time order:
while events:
process_next()
# Output: t=1, t=3, t=7, t=10 -- always in time orderБыстрая проверка
Проверьте, насколько хорошо Вы поняли концепции «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке Вы изучили: MinHeap и MaxHeap с нуля с операциями просеивания вверх и вниз, алгоритм построения кучи Флойда за O(n) и объяснение, почему он эффективнее пошаговой вставки за O(n log n), а также практические применения, включая k наиболее частых элементов и удаление по индексу. Далее мы рассмотрим модуль heapq в Python и приёмы работы с макс-кучей.
Часто задаваемые вопросы
Урок «Построение кучи, добавление и извлечение с нуля» бесплатный?
Да — полный текст урока «Построение кучи, добавление и извлечение с нуля» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Построение кучи, добавление и извлечение с нуля»?
Реализуйте просеивание вверх для добавления и просеивание вниз для извлечения, а затем постройте кучу из неотсортированного массива за O(n) с помощью алгоритма Флойда Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Построение кучи, добавление и извлечение с нуля»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Свойство кучи и представление массивом
- Построение кучи, добавление и извлечение с нуля
- heapq в Python и приёмы работы с максимальной кучей
- Медиана потока данных и слияние k списков