priority_queue_task3 - master - evabaraniuk/homework

priority_queue_task3
89 строк3 KB
evabaraniuk
update priority_queue_task3
07 июн 2025, 13:25
07 июн 2025, 13:257c3c889
from binary_heap import BinaryHeap

class PriorityQueue:
    
    def __init__(self, is_min_priority=True):
        self.heap = BinaryHeap(is_min_heap=is_min_priority)
        self.is_min_priority = is_min_priority
    
    def push(self, priority, item):
        self.heap.insert((priority, item))
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Priority queue is empty")
        priority, item = self.heap.extract_top()
        return priority, item
    
    def peek(self):
        if self.is_empty():
            raise IndexError("Priority queue is empty")
        return self.heap.heap[0]
    
    def is_empty(self):
        return len(self.heap.heap) == 0
    
    def size(self):
        return len(self.heap.heap)
    
    def build_from_list(self, items):
        self.heap.build(items)

# Специализированная версия для алгоритма Дейкстры
class DijkstraPriorityQueue(PriorityQueue):
    
    def __init__(self):
        super().__init__(is_min_priority=True)  # Минимальная куча для кратчайших расстояний
    
    def push_vertex(self, distance, vertex):
        self.push(distance, vertex)
    
    def pop_vertex(self):
        distance, vertex = self.pop()
        return distance, vertex
    
    def is_vertex_in_queue(self, vertex):
        for distance, v in self.heap.heap:
            if v == vertex:
                return True
        return False

if __name__ == "__main__":
    print("=== Тест обычной очереди с приоритетом ===")
    pq = PriorityQueue()
    
    # Добавляем элементы
    pq.push(3, "задача C")
    pq.push(1, "задача A") 
    pq.push(2, "задача B")
    pq.push(1, "задача A2")  # Одинаковый приоритет
    
    print("Размер очереди:", pq.size())
    
    # Извлекаем по приоритету
    while not pq.is_empty():
        priority, item = pq.pop()
        print(f"Приоритет {priority}: {item}")
    
    print("\nТест очереди для Дейкстры")
    dijkstra_pq = DijkstraPriorityQueue()
    
    # Добавляем вершины с расстояниями
    dijkstra_pq.push_vertex(5, 'A')
    dijkstra_pq.push_vertex(2, 'B')
    dijkstra_pq.push_vertex(8, 'C')
    dijkstra_pq.push_vertex(1, 'D')
    
    while not dijkstra_pq.is_empty():
        distance, vertex = dijkstra_pq.pop_vertex()
        print(f"Вершина {vertex} с расстоянием {distance}")
    
    print("\nТест build_from_list")
    pq2 = PriorityQueue()
    items = [(5, 'E'), (2, 'B'), (8, 'H'), (1, 'A'), (3, 'C')]
    pq2.build_from_list(items)
    
    print("Построение из списка:", items)
    while not pq2.is_empty():
        priority, item = pq2.pop()
        print(f"Приоритет {priority}: {item}")