Двоичный кучи - Очередь с приоритетом (Priority Queue)

Очередь с приоритетом (Priority Queue)

Очередь с приоритетом — это абстрактный тип данных, где каждый элемент имеет приоритет. Элементы извлекаются не в порядке добавления (как в обычной очереди), а в соответствии с их приоритетом: сначала элементы с наивысшим (или наименьшим) приоритетом.

Основные реализации:

1. Двоичная куча (наиболее распространенная)

2. Биномиальная куча

3. Фибоначчиева куча

Двоичная куча (Binary Heap)

Двоичная куча — это полное двоичное дерево, удовлетворяющее свойству кучи:

• Для max-heap: приоритет каждого узла ≥ приоритетов его потомков

• Для min-heap: приоритет каждого узла ≤ приоритетов его потомков

Сложность операций:

Реализация в Python (с использованием модуля heapq):

import heapq

# Создание min-heap (по умолчанию)
data = ['R', 'C', 'T', 'H', 'E', 'D', 'L']

# Преобразование списка в кучу
heapq.heapify(data)
print("Min-heap:", data)  # ['C', 'E', 'D', 'H', 'R', 'T', 'L']

# Добавление элемента
heapq.heappush(data, 'A')
print("После добавления 'A':", data)

# Извлечение элемента с наивысшим приоритетом (минимального)
min_item = heapq.heappop(data)
print("Извлеченный элемент:", min_item)
print("Куча после извлечения:", data)

# Реализация max-heap (используя отрицательные значения)
max_heap = []
for item in ['R', 'C', 'T', 'H', 'E', 'D', 'L']:
    heapq.heappush(max_heap, (-ord(item), item))  # Сортируем по отрицательному значению ASCII

print("\nMax-heap (как кортежи):", max_heap)
max_item = heapq.heappop(max_heap)[1]  # Извлекаем оригинальное значение
print("Извлеченный элемент с максимальным приоритетом:", max_item)

Пример кода:

class MinHeap:
    def __init__(self):
        self.heap = []
    
    def push(self, item):
        """Добавление элемента в кучу"""
        heapq.heappush(self.heap, item)
    
    def pop(self):
        """Извлечение минимального элемента"""
        return heapq.heappop(self.heap)
    
    def peek(self):
        """Просмотр минимального элемента без извлечения"""
        return self.heap[0] if self.heap else None
    
    def __len__(self):
        return len(self.heap)
    
    def __str__(self):
        return str(self.heap)

# Пример использования
heap = MinHeap()
heap.push(5)
heap.push(2)
heap.push(8)
heap.push(1)

print("\nПользовательская min-heap:")
print("Текущая куча:", heap)
print("Минимальный элемент:", heap.peek())
print("Извлеченный элемент:", heap.pop())
print("Куча после извлечения:", heap)