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

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

Пример 1: Базовое извлечение элемента

import heapq

heap = [3, 1, 4, 1, 5, 9]
heapq.heapify(heap)
print("Куча:", heap)

min_element = heapq.heappop(heap)
print("Извлеченный элемент:", min_element)
print("Куча после извлечения:", heap)

Куча: [1, 1, 4, 3, 5, 9]
Извлеченный элемент: 1
Куча после извлечения: [1, 3, 4, 9, 5]

Пример 2: Последовательное извлечение элементов

import heapq

heap = [5, 7, 9, 1, 3]
heapq.heapify(heap)

while heap:
    print(heapq.heappop(heap), end=' ')

1 3 5 7 9

Пример 3: Работа с пользовательскими объектами

import heapq

class Task:
    def __init__(self, priority, name):
        self.priority = priority
        self.name = name
    
    def __lt__(self, other):
        return self.priority < other.priority

heap = []
heapq.heappush(heap, Task(3, "Низкий приоритет"))
heapq.heappush(heap, Task(1, "Высокий приоритет"))
heapq.heappush(heap, Task(2, "Средний приоритет"))

while heap:
    task = heapq.heappop(heap)
    print(f"Приоритет: {task.priority}, Задача: {task.name}")

Приоритет: 1, Задача: Высокий приоритет
Приоритет: 2, Задача: Средний приоритет
Приоритет: 3, Задача: Низкий приоритет

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

heapq.heappushpop()

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

heapq.nsmallest()

Функция heapq.nsmallest() возвращает n наименьших элементов из итерируемого объекта. Полезна, когда нужно получить несколько минимальных значений без изменения исходной структуры данных.

Встроенная функция min()

Функция min() находит минимальный элемент в коллекции, но не удаляет его. Используется для разовых операций поиска минимума без необходимости поддерживать структуру кучи.

Выбор функции

heapq.heappop() предпочтительнее при работе с очередями с приоритетом и в алгоритмах, которые требуют многократного извлечения минимального элемента. min() лучше подходит для единичных операций поиска минимума. heapq.nsmallest() применяется, когда нужно получить несколько минимальных значений.

Альтернативы в других языках программирования

Java: PriorityQueue.poll()

import java.util.PriorityQueue;

PriorityQueue pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(3);
System.out.println(pq.poll()); // 1

1

JavaScript: Самописная реализация

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    pop() {
        if (this.heap.length === 0) return null;
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        return min;
    }
}

Go: container/heap.Pop()

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) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

h := &IntHeap{3, 1, 4}
heap.Init(h)
fmt.Println(heap.Pop(h)) // 1

C#: SortedSet.Min

using System.Collections.Generic;

var sortedSet = new SortedSet { 5, 1, 3 };
int min = sortedSet.Min;
sortedSet.Remove(min); // Удаление элемента

Kotlin: PriorityQueue.poll()

import java.util.PriorityQueue

val pq = PriorityQueue()
pq.add(5)
pq.add(1)
pq.add(3)
println(pq.poll()) // 1

1

Типичные ошибки при использовании

Ошибка 1: Извлечение из пустой кучи

import heapq

heap = []
try:
    heapq.heappop(heap)
except IndexError as e:
    print(f"Ошибка: {e}")

Ошибка: index out of range

Ошибка 2: Использование невалидной кучи

import heapq

# Список не преобразован в кучу
invalid_heap = [3, 2, 1, 4, 5]
print("Попытка извлечь из некорректной кучи:", heapq.heappop(invalid_heap))
print("Состояние после извлечения:", invalid_heap)

Попытка извлечь из некорректной кучи: 3
Состояние после извлечения: [2, 1, 4, 5]

Ошибка 3: Неправильное сравнение объектов

import heapq

class Item:
    def __init__(self, value):
        self.value = value

heap = []
heapq.heappush(heap, Item(3))
heapq.heappush(heap, Item(1))

# Вызовет TypeError при сравнении
# heapq.heappop(heap)

Для работы с пользовательскими объектами необходимо определить метод __lt__() для сравнения.

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

В Python 3.9 была добавлена поддержка аннотаций типов для функций модуля heapq. В Python 3.10 оптимизирована производительность операций с кучами, что особенно заметно при работе с большими объемами данных. Начиная с Python 3.11, улучшена обработка исключений при работе с некорректными кучами.

Семантика функции heapq.heappop() остается неизменной с момента ее введения, что обеспечивает обратную совместимость кода.

Расширенные примеры использования

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

import heapq
import time

class PriorityQueue:
    def __init__(self):
        self.heap = []
        self.counter = 0  # Для стабильности сортировки
    
    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, self.counter, item))
        self.counter += 1
    
    def pop(self):
        if not self.heap:
            raise IndexError("Очередь пуста")
        return heapq.heappop(self.heap)[-1]

pq = PriorityQueue()
pq.push("Задача A", 3)
pq.push("Задача B", 1)
pq.push("Задача C", 2)

print("Порядок выполнения:")
print(pq.pop())  # Задача B
print(pq.pop())  # Задача C
print(pq.pop())  # Задача A

Порядок выполнения:
Задача B
Задача C
Задача A

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

import heapq

def merge_sorted_sequences(sequences):
    heap = []
    
    # Инициализация кучи первыми элементами
    for i, seq in enumerate(sequences):
        if seq:
            heapq.heappush(heap, (seq[0], i, 0))
    
    result = []
    while heap:
        val, seq_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        
        # Добавляем следующий элемент из той же последовательности
        if elem_idx + 1 < len(sequences[seq_idx]):
            next_elem = sequences[seq_idx][elem_idx + 1]
            heapq.heappush(heap, (next_elem, seq_idx, elem_idx + 1))
    
    return result

seq1 = [1, 4, 7]
seq2 = [2, 5, 8]
seq3 = [3, 6, 9]

merged = merge_sorted_sequences([seq1, seq2, seq3])
print("Объединенная последовательность:", merged)

Объединенная последовательность: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Пример 3: Алгоритм Дейкстры с использованием кучи

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    
    while heap:
        current_distance, current_node = heapq.heappop(heap)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    
    return distances

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print("Кратчайшие расстояния от A:", dijkstra(graph, 'A'))

Кратчайшие расстояния от A: {'A': 0, 'B': 1, 'C': 3, 'D': 4}