Heapq.heapify: примеры (PYTHON)

Примеры использования heapq.heapify

Базовый пример с числовым списком:

import heapq

numbers = [7, 1, 5, 3, 9, 2]
print(f"До heapify: {numbers}")
heapq.heapify(numbers)
print(f"После heapify: {numbers}")
print(f"Минимальный элемент: {numbers[0]}")

До heapify: [7, 1, 5, 3, 9, 2]
После heapify: [1, 3, 2, 7, 9, 5]
Минимальный элемент: 1

Пример со списком кортежей (используется лексикографическое сравнение):

import heapq

tasks = [(3, 'задача C'), (1, 'задача A'), (2, 'задача B')]
heapq.heapify(tasks)
print(tasks)
first_task = heapq.heappop(tasks)
print(f"Первая задача: {first_task}")

[(1, 'задача A'), (3, 'задача C'), (2, 'задача B')]
Первая задача: (1, 'задача A')

Похожие функции в Python

Для работы с упорядоченными коллекциями в Python существуют другие инструменты:

• bisect.insort: Позволяет вставлять элементы в отсортированный список с сохранением порядка. В отличие от кучи, обеспечивает быструю вставку и доступ к отсортированным данным, но медленное удаление минимального элемента (O(n) vs O(log n) у кучи). Предпочтительнее при частых запросах к середине списка и редких удалениях.
• queue.PriorityQueue: Потокобезопасная реализация очереди с приоритетом, использующая модуль heapq внутри. Стоит выбирать при работе в многопоточных программах.
• sorted и list.sort: Полная сортировка списка. Используется, когда необходим полный упорядоченный список или частый доступ по индексу, а не только к минимальному элементу. Сортировка имеет сложность O(n log n), тогда как создание кучи - O(n).

Реализации кучи в других языках

Концепция кучи (обычно min-heap или max-heap) присутствует во многих языках, часто как часть стандартной библиотеки.

Java: Класс PriorityQueue из java.util. Отличие: создается отдельный объект, а не преобразуется список.

import java.util.PriorityQueue;

PriorityQueue heap = new PriorityQueue<>();
heap.add(7); heap.add(1); heap.add(5);
System.out.println(heap.peek()); // 1

1

JavaScript: Нет встроенной кучи, но можно реализовать или использовать библиотеки. Пример простой реализации.

Go: Пакет container/heap. Требуется реализация интерфейса heap.Interface.

import "container/heap"

// IntHeap - пример типа для кучи целых чисел
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    h := &IntHeap{7, 1, 5}
    heap.Init(h)
    fmt.Println((*h)[0]) // 1
}

1

C#: Класс PriorityQueue (до .NET 6 требовались сторонние реализации).

using System.Collections.Generic;

var heap = new PriorityQueue();
heap.Enqueue(element: 7, priority: 7);
heap.Enqueue(1, 1);
heap.Enqueue(5, 5);
heap.TryPeek(out int element, out _);
Console.WriteLine(element); // 1

1

Типичные ошибки

1. Ожидание возвращаемого значения. Функция модифицирует список на месте и возвращает None.

import heapq

lst = [5, 3, 8]
new_heap = heapq.heapify(lst) # ОШИБКА: new_heap будет None
print(new_heap)

None

2. Попытка использовать на неизменяемой или неподдерживаемой последовательности.

import heapq

tuple_data = (5, 3, 8) # Кортеж неизменяем
heapq.heapify(tuple_data) # TypeError

TypeError: heap argument must be a list

3. Непонимание, что куча не является отсортированным списком. После heapify список лишь удовлетворяет свойству кучи.

import heapq

lst = [5, 3, 8, 1]
heapq.heapify(lst)
print(f"Куча: {lst}")
print(f"Элементы по порядку: {[heapq.heappop(lst) for _ in range(4)]}")

Куча: [1, 3, 8, 5]
Элементы по порядку: [1, 3, 5, 8]

Изменения в последних версиях

В Python 3.x функция heapq.heapify не претерпела значительных изменений в плане сигнатуры или базового поведения. Она остается стабильной частью модуля heapq. Основные обновления касались внутренних оптимизаций и улучшения производительности, которые не влияют на публичный API. Модуль heapq был реализован на Python, а затем ключевые части переписаны на C для увеличения скорости. Эти изменения прозрачны для пользователя.

Расширенные примеры

Создание max-heap через инвертирование значений. Модуль heapq реализует только min-heap.

import heapq

data = [10, 5, 20, 15]
# Создаем max-heap, умножая значения на -1
max_heap = [-x for x in data]
heapq.heapify(max_heap)
print(f"Max-heap (внутренне): {max_heap}")
# Для извлечения максимума инвертируем обратно
max_value = -heapq.heappop(max_heap)
print(f"Максимальное значение: {max_value}")

Max-heap (внутренне): [-20, -15, -10, -5]
Максимальное значение: 20

Работа с пользовательскими объектами через ключевую функцию.

import heapq

class Task:
    def __init__(self, priority, name):
        self.priority = priority
        self.name = name
    def __repr__(self):
        return f"Task({self.priority}, '{self.name}')"

tasks = [Task(3, 'Низкий'), Task(1, 'Высокий'), Task(2, 'Средний')]
# Куча не может сравнивать объекты Task напрямую
# Используем кортежи (приоритет, объект)
task_heap = [(t.priority, t) for t in tasks]
heapq.heapify(task_heap)
print(f"Куча задач: {task_heap}")
_, next_task = heapq.heappop(task_heap)
print(f"Следующая задача: {next_task}")

Куча задач: [(1, Task(1, 'Высокий')), (3, Task(3, 'Низкий')), (2, Task(2, 'Средний'))]
Следующая задача: Task(1, 'Высокий')

Объединение нескольких куч после преобразования.

import heapq

list1 = [34, 25, 12]
list2 = [7, 11, 45]
heapq.heapify(list1)
heapq.heapify(list2)

# Мержим две кучи
merged = list1 + list2
heapq.heapify(merged)
print(f"Объединенная куча: {merged}")
sorted_result = [heapq.heappop(merged) for _ in range(6)]
print(f"Отсортированные элементы: {sorted_result}")

Объединенная куча: [7, 11, 12, 34, 25, 45]
Отсортированные элементы: [7, 11, 12, 25, 34, 45]

Эмуляция работы с потоком данных: добавление в кучу и периодическое извлечение минимума.

import heapq
import random

stream = [random.randint(1, 100) for _ in range(10)]
print(f"Поток данных: {stream}")

heap = []
for i, value in enumerate(stream, 1):
    heapq.heappush(heap, value) # Альтернатива: создать список и heapify
    if i % 4 == 0: # Каждые 4 элемента
        min_val = heapq.heappop(heap)
        print(f"Шаг {i}, минимум: {min_val}, текущая куча: {heap}")

Поток данных: [70, 4, 45, 86, 20, 35, 31, 39, 21, 11]
Шаг 4, минимум: 4, текущая куча: [20, 45, 70, 86]
Шаг 8, минимум: 20, текущая куча: [31, 45, 35, 86, 39]