0Pricing
Coding Interview Prep · Урок

Свойство кучи и представление массивом

Поймите структуру полного двоичного дерева, хранящегося в массиве, выведите формулы индексов родителей и потомков и визуализируйте операции просеивания вверх и вниз

«Свойство кучи и представление массивом» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Что такое куча

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

# Min-heap example:
#         1
#        / \
#       3   2
#      / \ / \
#     7  4 5  6
# Every parent <= its children
# Root (1) is always the minimum

# Max-heap example:
#         9
#        / \
#       7   8
#      / \ / \
#     3  4 5  6
# Every parent >= its children
# Root (9) is always the maximum
print('Heap property: parent dominates all descendants')

Структура полного двоичного дерева

Куча хранится как полное двоичное дерево — все уровни полностью заполнены, кроме, возможно, последнего, который заполняется слева направо. Именно эта структура позволяет использовать элегантное представление в виде массива без лишнего пространства и указателей. Свойство полноты гарантирует, что высота кучи всегда равна floor(log₂ n), обеспечивая операции push и pop за O(log n).

# Complete binary tree properties:
# 1. All levels filled except possibly the last
# 2. Last level filled from LEFT to right
# 3. For n nodes: height = floor(log2(n))

# NOT complete (last level not left-filled):
#     1
#    / \
#   2   3
#        \
#         4  <- right child without left sibling

# Valid complete binary tree with 4 nodes:
#     1
#    / \
#   2   3
#  /
# 4
print('Complete BT: height = floor(log2(n)) always')

Представление кучи в виде массива

Структура полного двоичного дерева позволяет хранить кучу в обычном массиве без указателей. Для узла с индексом i (индексация с нуля) его родитель находится по индексу (i-1) // 2, левый потомок — по индексу 2i+1, а правый потомок — по индексу 2i+2. Эти целочисленные вычисления заменяют обход по указателям и делают работу кучи особенно эффективной с точки зрения использования кэша.

# Array representation (0-indexed):
# Index:  0  1  2  3  4  5  6
# Array: [1, 3, 2, 7, 4, 5, 6]
# Tree:        1          (index 0)
#             / \         
#            3   2        (indices 1, 2)
#           / \ / \       
#          7  4 5  6      (indices 3,4,5,6)

# Index formulas (0-based):
def parent(i):      return (i - 1) // 2
def left_child(i):  return 2 * i + 1
def right_child(i): return 2 * i + 2

heap = [1, 3, 2, 7, 4, 5, 6]
print('Parent of index 3:', parent(3), '-> value', heap[parent(3)])
print('Left child of 1:', left_child(1), '-> value', heap[left_child(1)])

Просеивание вверх: восстановление кучи после вставки

Просеивание вверх (также называемое подъёмом или просеиванием вверх при построении кучи) выполняется после вставки нового элемента в конец массива кучи. Сравните новый элемент с его родителем; если свойство кучи нарушено, поменяйте их местами и продолжайте двигаться вверх. Повторяйте эти действия, пока элемент не окажется на правильной позиции или не достигнет корня. Операция выполняется за O(log n), поскольку высота дерева равна O(log n).

def sift_up(heap, i):
    while i > 0:
        p = (i - 1) // 2  # parent index
        if heap[p] > heap[i]:  # min-heap: parent should be smaller
            heap[p], heap[i] = heap[i], heap[p]
            i = p
        else:
            break  # heap property restored

# Demonstrate: insert 0 into an existing min-heap
heap = [1, 3, 2, 7, 4, 5, 6]
heap.append(0)  # add at end
print('Before sift-up:', heap)
sift_up(heap, len(heap) - 1)
print('After sift-up:', heap)  # 0 should bubble to root

Просеивание вниз: восстановление кучи после извлечения

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

def sift_down(heap, i, n):
    while True:
        smallest = i
        l = 2 * i + 1  # left child
        r = 2 * i + 2  # right child
        if l < n and heap[l] < heap[smallest]:
            smallest = l
        if r < n and heap[r] < heap[smallest]:
            smallest = r
        if smallest == i:
            break  # already in correct position
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

heap = [1, 3, 2, 7, 4, 5, 6]
# Pop min: move last to root, then sift-down
heap[0] = heap[-1]
heap.pop()
print('After move last to root:', heap)
sift_down(heap, 0, len(heap))
print('After sift-down:', heap)  # valid min-heap again

Построение кучи из массива: алгоритм Флойда

Наивная вставка n элементов по одному выполняется за O(n log n). Алгоритм построения кучи Флойда строит кучу за O(n), применяя просеивание вниз к каждому внутреннему узлу, начиная с последнего внутреннего узла (индекс n//2 - 1) и двигаясь к корню. Листья уже являются тривиальными кучами, поэтому нужно исправить только внутренние узлы — именно поэтому суммарная трудоёмкость составляет O(n), а не O(n log n).

def build_heap(arr):
    n = len(arr)
    # Start from last non-leaf node: index n//2 - 1
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)
    return arr

arr = [5, 3, 8, 1, 9, 2, 7]
print('Before:', arr)
build_heap(arr)
print('After (min-heap):', arr)  # root should be 1

# Why O(n)? Most nodes are near the bottom (leaves).
# Level k from bottom has ~n/2^k nodes, each needing
# at most k swaps. Sum = n * sum(k/2^k) = O(n).

Пирамидальная сортировка с использованием кучи-массива

Пирамидальная сортировка выполняется за O(n log n) и использует O(1) дополнительной памяти. Этап 1: построить из массива max-heap за O(n). Этап 2: многократно извлекать максимум, меняя корень местами с последним неотсортированным элементом, а затем выполняя просеивание вниз в уменьшенной куче. После n извлечений массив будет отсортирован по возрастанию. Этот алгоритм работает на месте и показывает, как представление в виде массива позволяет выполнять сортировку без выделения отдельной структуры данных.

def sift_down_max(arr, i, n):
    while True:
        largest = i
        l, r = 2*i+1, 2*i+2
        if l < n and arr[l] > arr[largest]: largest = l
        if r < n and arr[r] > arr[largest]: largest = r
        if largest == i: break
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

def heap_sort(arr):
    n = len(arr)
    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        sift_down_max(arr, i, n)
    # Extract elements one by one
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]  # move max to end
        sift_down_max(arr, 0, end)

arr = [5, 3, 8, 1, 9, 2, 7]
heap_sort(arr)
print(arr)  # [1, 2, 3, 5, 7, 8, 9]

Min-heap и max-heap

В min-heap минимальный элемент находится в корне, поэтому операция извлечения всегда возвращает минимум. В max-heap в корне находится максимальный элемент, поэтому операция извлечения всегда возвращает максимум. Структура и операции у них одинаковы — меняется только направление сравнения. Модуль Python heapq реализует только min-heap, поэтому для имитации max-heap необходимо менять знаки значений.

import heapq

# Python heapq is a MIN-HEAP
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print('Min-heap min:', heapq.heappop(min_heap))  # 1

# Simulate MAX-HEAP by negating values
max_heap = []
for val in [5, 1, 3]:
    heapq.heappush(max_heap, -val)  # negate on push
print('Max-heap max:', -heapq.heappop(max_heap))  # 5 (negate on pop)

# For tuples: heapq sorts by first element
print(min_heap, max_heap)

Сложность операций с кучей: краткий обзор

Все операции с кучей основаны на просеивании вверх и просеивании вниз, каждое из которых выполняется за O(log n). Push: добавление в конец + просеивание вверх = O(log n). Pop: обмен корня с последним элементом + просеивание вниз = O(log n). Peek: обращение к индексу 0 = O(1). Построение кучи: O(n) с помощью алгоритма Флойда. Пирамидальная сортировка: O(n log n). Благодаря такой сложности кучи идеально подходят, когда из изменяющейся коллекции требуется многократно получать минимум или максимум.

# Heap complexity summary:
# Operation     | Time       | Space
# --------------|------------|-------
# Push          | O(log n)   | O(1)
# Pop (min/max) | O(log n)   | O(1)
# Peek          | O(1)       | O(1)
# Build from n  | O(n)       | O(1) in-place
# Heap sort     | O(n log n) | O(1)
# nlargest(k,n) | O(n log k) | O(k)

import heapq
data = [5, 3, 8, 1, 9, 2, 7]
print('Top 3 largest:', heapq.nlargest(3, data))  # [9, 8, 7]
print('Top 3 smallest:', heapq.nsmallest(3, data))  # [1, 2, 3]

Практические шаблоны использования куч на собеседованиях

Кучи позволяют решать целый класс задач с собеседований по общему шаблону: поддерживать очередь с приоритетом из k кандидатов при последовательной обработке n элементов. Поиск k наиболее часто встречающихся элементов, k ближайших к началу координат точек и планировщик задач используют этот шаблон. Узнать его можно по формулировке: «дан поток из n элементов, поддерживайте k лучших» — здесь всегда нужна куча размера k, что даёт общую временную сложность O(n log k).

import heapq

# Top-K closest points to origin using a max-heap of size k
def k_closest(points, k):
    # Use max-heap (negate distance) of size k
    heap = []
    for x, y in points:
        dist = -(x*x + y*y)  # negate for max-heap
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)  # remove farthest
    return [[x, y] for _, x, y in heap]

points = [[1,3], [-2,2], [5,8], [0,1]]
print(k_closest(points, 2))  # 2 closest to origin

Компромиссы при выборе между кучей и отсортированным массивом

Выбирайте кучу, если Вам нужен только многократный доступ к минимуму или максимуму и коллекция динамически изменяется. Выбирайте отсортированный массив, если нужен произвольный доступ по индексу или запросы по диапазону. Слабая сторона кучи — поиск произвольного элемента за O(n); её преимущество — вставка и удаление за O(log n), а также доступ к минимуму или максимуму за O(1). В отсортированном массиве вставка выполняется за O(n), но поиск с помощью двоичного поиска — за O(log n).

# Trade-off comparison:
# Structure     | insert  | delete_min | search | range_query
# --------------|---------|------------|--------|------------
# Min-heap      | O(logn) | O(logn)    | O(n)   | O(n)
# Sorted array  | O(n)    | O(n)       | O(logn)| O(logn+k)
# BST (balanced)| O(logn) | O(logn)    | O(logn)| O(logn+k)
# Hash map      | O(1)    | O(1)       | O(1)   | O(n)

# Interview heuristic:
# 'Find minimum repeatedly from dynamic collection' -> HEAP
# 'Binary search or range query' -> sorted array or BST
# 'Fast lookup by key' -> hash map
print('Heap = dynamic collection with priority access')

Быстрая проверка

Проверьте своё понимание концепций структур данных и алгоритмов — подготовки к собеседованиям по программированию, рассмотренных в этом уроке.

Итоги урока

В этом уроке Вы изучили свойство кучи и структуру полного двоичного дерева, представление в виде массива с формулами индексов родителя и потомков, а также просеивание вверх и просеивание вниз как строительные блоки всех операций с кучей, включая построение за O(n) по алгоритму Флойда. Далее мы реализуем heapify и изучим модуль Python heapq.

Часто задаваемые вопросы

Урок «Свойство кучи и представление массивом» бесплатный?

Да — полный текст урока «Свойство кучи и представление массивом» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Свойство кучи и представление массивом»?

Поймите структуру полного двоичного дерева, хранящегося в массиве, выведите формулы индексов родителей и потомков и визуализируйте операции просеивания вверх и вниз Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Свойство кучи и представление массивом»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Свойство кучи и представление массивом
  2. Построение кучи, добавление и извлечение с нуля
  3. heapq в Python и приёмы работы с максимальной кучей
  4. Медиана потока данных и слияние k списков
← Назад к Coding Interview Prep