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

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

import heapq

# Пример 1: Добавление чисел
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 10)
print(heap)

[2, 5, 10]

# Пример 2: Добавление кортежей (приоритет + данные)
heap = []
heapq.heappush(heap, (3, 'Задача C'))
heapq.heappush(heap, (1, 'Задача A'))
heapq.heappush(heap, (2, 'Задача B'))
print(heap)

[(1, 'Задача A'), (3, 'Задача C'), (2, 'Задача B')]

# Пример 3: Использование с пользовательскими объектами через __lt__
class Task:
    def __init__(self, priority, name):
        self.priority = priority
        self.name = name
    def __lt__(self, other):
        return self.priority < other.priority

heap = []
tasks = [Task(3, 'C'), Task(1, 'A'), Task(2, 'B')]
for task in tasks:
    heapq.heappush(heap, task)
print([(t.priority, t.name) for t in heap])

[(1, 'A'), (3, 'C'), (2, 'B')]

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

heapq.heappushpop(heap, item): добавляет элемент и сразу извлекает минимальный. Эффективнее последовательного вызова heappush и heappop.

heapq.heapify(x): преобразует список в кучу за линейное время. Используется для инициализации кучи из существующего списка.

heapq.heappop(heap): извлекает и возвращает минимальный элемент кучи.

queue.PriorityQueue: потокобезопасная очередь с приоритетом на основе кучи. Предоставляет интерфейс с методами put и get.

Выбор зависит от задачи. heapq.heappush подходит для ручного управления кучей. PriorityQueue предпочтительнее в многопоточных приложениях.

Аналоги в других языках

Java

import java.util.PriorityQueue;
PriorityQueue heap = new PriorityQueue<>();
heap.add(5);
heap.add(2);
System.out.println(heap);

[2, 5]

Класс PriorityQueue по умолчанию создает минимальную кучу.

JavaScript

// Нет встроенной кучи. Обычно используют массив и функции.
const heap = [];
function heappush(heap, item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
        const parent = Math.floor((i - 1) / 2);
        if (heap[parent] <= heap[i]) break;
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
    }
}
heappush(heap, 5);
heappush(heap, 2);
console.log(heap);

[2, 5]

Go

import "container/heap"
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 main() {
    h := &IntHeap{5}
    heap.Init(h)
    heap.Push(h, 2)
    fmt.Println(h)
}

&[2 5]

В Go требуется реализация интерфейса heap.Interface.

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

1. Передача не списка

import heapq
heap = (1, 2, 3)  # кортеж
heapq.heappush(heap, 4)

AttributeError: 'tuple' object has no attribute 'append'

Аргумент heap должен быть изменяемым списком.

2. Несравнимые элементы

import heapq
heap = [{'a': 1}, {'b': 2}]  # словари нельзя сравнивать по умолчанию
heapq.heappush(heap, {'c': 3})

TypeError: '<' not supported between instances of 'dict' and 'dict'

Элементы кучи должны поддерживать операции сравнения.

3. Нарушение инварианта кучи

import heapq
heap = [3, 1, 2]
heapq.heappush(heap, 0)
# Куча выглядит как [0, 1, 2, 3], но если список не был инициализирован как куча:
heap2 = [5, 8, 1]
heapq.heappush(heap2, 0)
print(heap2)

[0, 8, 1, 5]  # Не минимальная куча, т.к. 1 > 0, но 1 - правый потомок

Перед использованием списка как кучи его нужно инициализировать с помощью heapq.heapify или начинать с пустого.

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

В Python 3.10 функция heapq.heappush не претерпела значительных изменений в сигнатуре или поведении. Однако в Python 3.13 добавлена новая функция heapq.heappush_max для работы с максимальной кучей в модуле heapq. Основная функция heappush остается стабильной.

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

1. Реализация очереди с приоритетом для задач

import heapq
import time

class PriorityQueue:
    def __init__(self):
        self._heap = []
        self._counter = 0  # для сохранения порядка при одинаковых приоритетах

    def push(self, priority, item):
        # Используем кортеж (приоритет, счётчик, задача)
        # При сравнении кортежей сначала сравнивается приоритет, затем счётчик
        heapq.heappush(self._heap, (priority, self._counter, item))
        self._counter += 1

    def pop(self):
        return heapq.heappop(self._heap)[-1]  # возвращаем только задачу

pq = PriorityQueue()
pq.push(2, 'Помыть посуду')
pq.push(1, 'Сделать отчёт')
pq.push(2, 'Купить продукты')
print(pq.pop())
print(pq.pop())
print(pq.pop())

Сделать отчёт
Помыть посуду
Купить продукты

2. Объединение нескольких отсортированных последовательностей

import heapq

def merge_sorted_lists(*lists):
    heap = []
    # Помещаем первый элемент каждого списка с идентификатором списка
    for list_idx, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], list_idx, 0))
    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        next_idx = elem_idx + 1
        if next_idx < len(lists[list_idx]):
            next_val = lists[list_idx][next_idx]
            heapq.heappush(heap, (next_val, list_idx, next_idx))
    return result

list1 = [1, 4, 7]
list2 = [2, 5, 8]
list3 = [3, 6, 9]
print(merge_sorted_lists(list1, list2, list3))

[1, 2, 3, 4, 5, 6, 7, 8, 9]

3. Поддержка максимальной кучи через инвертирование приоритета

import heapq

class MaxHeap:
    def __init__(self):
        self.heap = []
    def push(self, val):
        heapq.heappush(self.heap, -val)  # Инвертируем значение
    def pop(self):
        return -heapq.heappop(self.heap)
    def peek(self):
        return -self.heap[0]

maxheap = MaxHeap()
for x in [3, 1, 4, 1, 5, 9]:
    maxheap.push(x)
print([maxheap.pop() for _ in range(3)])

[9, 5, 4]