Пирамидальная сортировка (Heap Sort): полное руководство с примерами

Почему Heap Sort важен?

Пирамидальная сортировка (Heap Sort) — это мощный алгоритм, объединяющий эффективность и экономию памяти:

• 🎯 Гарантированная сложность O(n log n) в любом случае
• 💾 Сортировка "на месте" — O(1) дополнительной памяти
• 🏗️ Основан на структуре данных "куча" (heap)
• 🔧 Используется в приоритетных очередях и планировщиках задач
• 💼 Частый вопрос на собеседованиях в топовых IT-компаниях

Что такое куча (Heap)?

Прежде чем разбирать Heap Sort, необходимо понять структуру данных куча.

Определение кучи

Куча (Heap) — это полное бинарное дерево, удовлетворяющее свойству кучи:

• Max-Heap: значение каждого узла больше или равно значениям его потомков
• Min-Heap: значение каждого узла меньше или равно значениям его потомков

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

// Куча хранится в массиве, где для элемента с индексом i:
// - Родитель:      Math.floor((i - 1) / 2)
// - Левый потомок: 2 * i + 1
// - Правый потомок: 2 * i + 2

// Пример Max-Heap:
//           90
//          /  \
//        80    70
//       / \   / \
//      60 50 40 30

// В массиве: [90, 80, 70, 60, 50, 40, 30]
// Индексы:    0   1   2   3   4   5   6

Визуализация свойств кучи

// Max-Heap: родитель >= потомки
//      [90]          <- максимум всегда в корне
//      /  \
//   [80]  [70]       <- 80 >= 60, 50  и  70 >= 40, 30
//   /  \   /  \
// [60][50][40][30]

// Это НЕ куча (нарушено свойство):
//      [50]
//      /  \
//   [80]  [70]       <- 80 > 50 — нарушение!

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Принцип работы Heap Sort

Heap Sort работает в два этапа:

Этап 1: Построение Max-Heap (heapify)

Преобразуем массив в Max-Heap, где максимальный элемент находится в корне.

Этап 2: Извлечение элементов

1. Меняем корень (максимум) с последним элементом
2. Уменьшаем размер кучи на 1
3. Восстанавливаем свойство кучи для нового корня
4. Повторяем, пока куча не опустеет

Пошаговая визуализация

// Исходный массив: [4, 10, 3, 5, 1]

// Шаг 1: Строим Max-Heap
// [4, 10, 3, 5, 1] -> [10, 5, 3, 4, 1]
//
//       10
//      /  \
//     5    3
//    / \
//   4   1

// Шаг 2: Извлекаем максимумы
// Меняем 10 и 1: [1, 5, 3, 4, 10] -> heapify -> [5, 4, 3, 1, | 10]
// Меняем 5 и 1:  [1, 4, 3, 5, 10] -> heapify -> [4, 1, 3, | 5, 10]
// Меняем 4 и 3:  [3, 1, 4, 5, 10] -> heapify -> [3, 1, | 4, 5, 10]
// Меняем 3 и 1:  [1, 3, 4, 5, 10] -> heapify -> [1, | 3, 4, 5, 10]

// Результат: [1, 3, 4, 5, 10]

Реализации Heap Sort на JavaScript

Решение 1: Классическая реализация

function heapSort(arr) {
  const n = arr.length;

  // Шаг 1: Построение Max-Heap
  // Начинаем с последнего не-листового узла
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // Шаг 2: Извлечение элементов из кучи
  for (let i = n - 1; i > 0; i--) {
    // Перемещаем текущий корень (максимум) в конец
    [arr[0], arr[i]] = [arr[i], arr[0]];

    // Восстанавливаем свойство кучи для уменьшенной кучи
    heapify(arr, i, 0);
  }

  return arr;
}

function heapify(arr, heapSize, rootIndex) {
  let largest = rootIndex;
  const left = 2 * rootIndex + 1;
  const right = 2 * rootIndex + 2;

  // Проверяем, больше ли левый потомок корня
  if (left < heapSize && arr[left] > arr[largest]) {
    largest = left;
  }

  // Проверяем, больше ли правый потомок текущего наибольшего
  if (right < heapSize && arr[right] > arr[largest]) {
    largest = right;
  }

  // Если наибольший элемент не корень
  if (largest !== rootIndex) {
    [arr[rootIndex], arr[largest]] = [arr[largest], arr[rootIndex]];

    // Рекурсивно применяем heapify к поддереву
    heapify(arr, heapSize, largest);
  }
}

// Пример использования
const array = [4, 10, 3, 5, 1, 8, 7];
console.log(heapSort(array)); // [1, 3, 4, 5, 7, 8, 10]

Анализ решения:

• Сортировка "на месте" — O(1) дополнительной памяти
• Гарантированная сложность O(n log n)
• Не стабильный алгоритм

Решение 2: Итеративный heapify (без рекурсии)

function heapSortIterative(arr) {
  const n = arr.length;

  // Построение Max-Heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapifyIterative(arr, n, i);
  }

  // Извлечение элементов
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapifyIterative(arr, i, 0);
  }

  return arr;
}

function heapifyIterative(arr, heapSize, rootIndex) {
  while (true) {
    let largest = rootIndex;
    const left = 2 * rootIndex + 1;
    const right = 2 * rootIndex + 2;

    if (left < heapSize && arr[left] > arr[largest]) {
      largest = left;
    }

    if (right < heapSize && arr[right] > arr[largest]) {
      largest = right;
    }

    if (largest === rootIndex) {
      break;
    }

    [arr[rootIndex], arr[largest]] = [arr[largest], arr[rootIndex]];
    rootIndex = largest;
  }
}

// Пример использования
const array = [4, 10, 3, 5, 1, 8, 7];
console.log(heapSortIterative(array)); // [1, 3, 4, 5, 7, 8, 10]

Преимущества итеративного подхода:

• Нет риска переполнения стека
• Немного эффективнее по памяти

Решение 3: Min-Heap для сортировки по убыванию

function heapSortDescending(arr) {
  const n = arr.length;

  // Построение Min-Heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    minHeapify(arr, n, i);
  }

  // Извлечение минимумов
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    minHeapify(arr, i, 0);
  }

  return arr;
}

function minHeapify(arr, heapSize, rootIndex) {
  let smallest = rootIndex;
  const left = 2 * rootIndex + 1;
  const right = 2 * rootIndex + 2;

  if (left < heapSize && arr[left] < arr[smallest]) {
    smallest = left;
  }

  if (right < heapSize && arr[right] < arr[smallest]) {
    smallest = right;
  }

  if (smallest !== rootIndex) {
    [arr[rootIndex], arr[smallest]] = [arr[smallest], arr[rootIndex]];
    minHeapify(arr, heapSize, smallest);
  }
}

// Пример использования
const array = [4, 10, 3, 5, 1, 8, 7];
console.log(heapSortDescending(array)); // [10, 8, 7, 5, 4, 3, 1]

Решение 4: Класс Heap с полным функционалом

class MaxHeap {
  constructor() {
    this.heap = [];
  }

  getParentIndex(i) {
    return Math.floor((i - 1) / 2);
  }

  getLeftChildIndex(i) {
    return 2 * i + 1;
  }

  getRightChildIndex(i) {
    return 2 * i + 2;
  }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  insert(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.heap[parentIndex] >= this.heap[index]) break;
      this.swap(parentIndex, index);
      index = parentIndex;
    }
  }

  extractMax() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return max;
  }

  bubbleDown(index) {
    const length = this.heap.length;

    while (true) {
      let largest = index;
      const left = this.getLeftChildIndex(index);
      const right = this.getRightChildIndex(index);

      if (left < length && this.heap[left] > this.heap[largest]) {
        largest = left;
      }

      if (right < length && this.heap[right] > this.heap[largest]) {
        largest = right;
      }

      if (largest === index) break;

      this.swap(index, largest);
      index = largest;
    }
  }

  sort() {
    const sorted = [];
    while (this.heap.length > 0) {
      sorted.unshift(this.extractMax());
    }
    return sorted;
  }
}

// Пример использования
const heap = new MaxHeap();
[4, 10, 3, 5, 1, 8, 7].forEach((val) => heap.insert(val));
console.log(heap.sort()); // [1, 3, 4, 5, 7, 8, 10]

Реализация на Python

Классическая реализация

def heap_sort(arr: list) -> list:
    """
    Пирамидальная сортировка

    Args:
        arr: Массив для сортировки

    Returns:
        Отсортированный массив
    """
    n = len(arr)

    # Построение Max-Heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Извлечение элементов из кучи
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

    return arr


def heapify(arr: list, heap_size: int, root_index: int) -> None:
    """
    Восстановление свойства кучи

    Args:
        arr: Массив
        heap_size: Текущий размер кучи
        root_index: Индекс корня поддерева
    """
    largest = root_index
    left = 2 * root_index + 1
    right = 2 * root_index + 2

    if left < heap_size and arr[left] > arr[largest]:
        largest = left

    if right < heap_size and arr[right] > arr[largest]:
        largest = right

    if largest != root_index:
        arr[root_index], arr[largest] = arr[largest], arr[root_index]
        heapify(arr, heap_size, largest)


# Пример использования
array = [4, 10, 3, 5, 1, 8, 7]
print(heap_sort(array))  # [1, 3, 4, 5, 7, 8, 10]

Python: Использование модуля heapq

import heapq


def heap_sort_with_heapq(arr: list) -> list:
    """
    Heap Sort с использованием стандартной библиотеки

    Args:
        arr: Массив для сортировки

    Returns:
        Отсортированный массив
    """
    # heapq реализует Min-Heap
    heap = arr.copy()
    heapq.heapify(heap)

    return [heapq.heappop(heap) for _ in range(len(heap))]


# Пример использования
array = [4, 10, 3, 5, 1, 8, 7]
print(heap_sort_with_heapq(array))  # [1, 3, 4, 5, 7, 8, 10]

Python: Класс MaxHeap

class MaxHeap:
    """Реализация Max-Heap с полным функционалом"""

    def __init__(self):
        self.heap = []

    def parent(self, i: int) -> int:
        return (i - 1) // 2

    def left_child(self, i: int) -> int:
        return 2 * i + 1

    def right_child(self, i: int) -> int:
        return 2 * i + 2

    def insert(self, value) -> None:
        """Вставка элемента в кучу"""
        self.heap.append(value)
        self._bubble_up(len(self.heap) - 1)

    def _bubble_up(self, index: int) -> None:
        """Всплытие элемента вверх"""
        while index > 0:
            parent_idx = self.parent(index)
            if self.heap[parent_idx] >= self.heap[index]:
                break
            self.heap[parent_idx], self.heap[index] = \
                self.heap[index], self.heap[parent_idx]
            index = parent_idx

    def extract_max(self):
        """Извлечение максимального элемента"""
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        max_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._bubble_down(0)
        return max_val

    def _bubble_down(self, index: int) -> None:
        """Погружение элемента вниз"""
        size = len(self.heap)

        while True:
            largest = index
            left = self.left_child(index)
            right = self.right_child(index)

            if left < size and self.heap[left] > self.heap[largest]:
                largest = left

            if right < size and self.heap[right] > self.heap[largest]:
                largest = right

            if largest == index:
                break

            self.heap[index], self.heap[largest] = \
                self.heap[largest], self.heap[index]
            index = largest

    def sort(self) -> list:
        """Сортировка через извлечение всех элементов"""
        result = []
        while self.heap:
            result.insert(0, self.extract_max())
        return result


# Пример использования
heap = MaxHeap()
for val in [4, 10, 3, 5, 1, 8, 7]:
    heap.insert(val)
print(heap.sort())  # [1, 3, 4, 5, 7, 8, 10]

Временная и пространственная сложность

Временная сложность

Почему построение кучи O(n), а не O(n log n)?

// Интуитивно кажется: n вставок * O(log n) = O(n log n)
// Но при bottom-up построении:

// Уровень 0 (листья): n/2 узлов, 0 операций heapify
// Уровень 1: n/4 узлов, максимум 1 операция каждый
// Уровень 2: n/8 узлов, максимум 2 операции каждый
// ...
// Уровень log n: 1 узел, максимум log n операций

// Сумма: n/4 * 1 + n/8 * 2 + n/16 * 3 + ... = O(n)

Пространственная сложность

• O(1) — сортировка выполняется "на месте"
• O(log n) — для стека рекурсии в heapify (можно избежать итеративной версией)

Сравнение с другими алгоритмами

Когда выбирать Heap Sort?

Используйте Heap Sort когда:

• Критична память — нужна сортировка O(1)
• Нужна гарантированная сложность O(n log n)
• Работаете с потоковыми данными (приоритетная очередь)
• Нужны только k наибольших/наименьших элементов

Не используйте когда:

• Важна стабильность сортировки
• Данные почти отсортированы (Quick Sort быстрее на практике)
• Критична cache-эффективность

Применения кучи и Heap Sort

1. Приоритетная очередь

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

  enqueue(value, priority) {
    this.heap.push({ value, priority });
    this.bubbleUp(this.heap.length - 1);
  }

  dequeue() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop().value;

    const max = this.heap[0].value;
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return max;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex].priority >= this.heap[index].priority) break;
      [this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ];
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    const length = this.heap.length;

    while (true) {
      let largest = index;
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      if (
        left < length &&
        this.heap[left].priority > this.heap[largest].priority
      ) {
        largest = left;
      }

      if (
        right < length &&
        this.heap[right].priority > this.heap[largest].priority
      ) {
        largest = right;
      }

      if (largest === index) break;

      [this.heap[index], this.heap[largest]] = [
        this.heap[largest],
        this.heap[index],
      ];
      index = largest;
    }
  }
}

// Пример: планировщик задач
const taskQueue = new PriorityQueue();
taskQueue.enqueue('Low priority task', 1);
taskQueue.enqueue('Critical task', 10);
taskQueue.enqueue('Medium task', 5);

console.log(taskQueue.dequeue()); // "Critical task"
console.log(taskQueue.dequeue()); // "Medium task"

2. Поиск K наибольших элементов

function findKLargest(arr, k) {
  // Строим Min-Heap размера k
  const minHeap = arr.slice(0, k);

  // Heapify
  for (let i = Math.floor(k / 2) - 1; i >= 0; i--) {
    minHeapify(minHeap, k, i);
  }

  // Проходим по остальным элементам
  for (let i = k; i < arr.length; i++) {
    if (arr[i] > minHeap[0]) {
      minHeap[0] = arr[i];
      minHeapify(minHeap, k, 0);
    }
  }

  return minHeap;
}

function minHeapify(arr, size, index) {
  let smallest = index;
  const left = 2 * index + 1;
  const right = 2 * index + 2;

  if (left < size && arr[left] < arr[smallest]) smallest = left;
  if (right < size && arr[right] < arr[smallest]) smallest = right;

  if (smallest !== index) {
    [arr[index], arr[smallest]] = [arr[smallest], arr[index]];
    minHeapify(arr, size, smallest);
  }
}

// Пример
const array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(findKLargest(array, 3)); // [5, 6, 9] (в виде min-heap)

3. Медиана потока данных

class MedianFinder {
  constructor() {
    this.maxHeap = []; // Левая половина (меньшие элементы)
    this.minHeap = []; // Правая половина (большие элементы)
  }

  addNum(num) {
    // Добавляем в maxHeap
    this.maxHeap.push(num);
    this.bubbleUpMax(this.maxHeap.length - 1);

    // Перемещаем максимум в minHeap
    const max = this.extractMaxFromMaxHeap();
    this.minHeap.push(max);
    this.bubbleUpMin(this.minHeap.length - 1);

    // Балансируем размеры
    if (this.minHeap.length > this.maxHeap.length) {
      const min = this.extractMinFromMinHeap();
      this.maxHeap.push(min);
      this.bubbleUpMax(this.maxHeap.length - 1);
    }
  }

  findMedian() {
    if (this.maxHeap.length > this.minHeap.length) {
      return this.maxHeap[0];
    }
    return (this.maxHeap[0] + this.minHeap[0]) / 2;
  }

  // ... вспомогательные методы для работы с кучами
}

Распространенные ошибки

1. Неправильные индексы потомков: 2*i + 1 и 2*i + 2, не 2*i и 2*i + 1

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

3. Путаница Max-Heap и Min-Heap: Для сортировки по возрастанию используйте Max-Heap

4. Неправильный диапазон построения: Начинаем с n/2 - 1, не с n - 1

Интересные факты

• Heap Sort был изобретен Дж. У. Дж. Уильямсом в 1964 году
• Структура данных "куча" используется в алгоритме Дейкстры
• Heapsort — единственный алгоритм с O(n log n) и O(1) памятью
• Linux использует кучу в планировщике процессов

Заключение

Пирамидальная сортировка — это элегантный алгоритм с уникальными свойствами:

• Гарантированная сложность O(n log n) без худших случаев
• Минимальное использование памяти — O(1)
• Основа для приоритетных очередей и многих других структур
• Эффективен для поиска K наибольших/наименьших элементов

Понимание кучи и Heap Sort открывает двери к решению множества практических задач — от планирования задач до обработки потоковых данных.