# Python's heapq module provides an implementation of the heap queue algorithm.
# Heaps are binary trees where the parent node is always smaller than (or equal to)
# its children for a min-heap, or larger than for a max-heap.
# The heapq module implements a min-heap.

import heapq

# Initialize an empty heap
min_heap = []
print(f"Initial heap: {min_heap}")

# 1. heappush(heap, item): Add an item to the heap, maintaining the heap property.
print("\n--- Pushing elements ---")
heapq.heappush(min_heap, 4)
print(f"After pushing 4: {min_heap}")
heapq.heappush(min_heap, 1)
print(f"After pushing 1: {min_heap}")
heapq.heappush(min_heap, 7)
print(f"After pushing 7: {min_heap}")
heapq.heappush(min_heap, 2)
print(f"After pushing 2: {min_heap}")
heapq.heappush(min_heap, 10)
print(f"After pushing 10: {min_heap}")

# Observe: The smallest element is always at index 0 (root of the min-heap).
# The rest of the list is NOT fully sorted, but maintains the heap property.
# This means min_heap[k] <= min_heap[2*k + 1] and min_heap[k] <= min_heap[2*k + 2]

# 2. heappop(heap): Remove and return the smallest item from the heap.
# This operation is O(log n) because the heap must be re-balanced.
print("\n--- Popping elements ---")
print(f"Smallest element popped: {heapq.heappop(min_heap)}") # Should be 1
print(f"Heap after pop: {min_heap}")
print(f"Next smallest element popped: {heapq.heappop(min_heap)}") # Should be 2
print(f"Heap after pop: {min_heap}")

# 3. heapify(x): Transform a list x into a heap, in-place, in O(n) time.
print("\n--- Heapifying a list ---")
unordered_list = [5, 1, 8, 3, 2, 9]
print(f"Unordered list: {unordered_list}")
heapq.heapify(unordered_list)
print(f"Heapified list: {unordered_list}")

# To simulate a max-heap using Python's min-heap:
# Store elements as their negative values.
print("\n--- Simulating a Max-Heap ---")
max_heap = []
heapq.heappush(max_heap, -4)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -7)
heapq.heappush(max_heap, -2)
print(f"Max-heap (internal): {max_heap}")
print(f"Largest element popped: {-heapq.heappop(max_heap)}") # Returns -1, so we negate it to get 1
print(f"Next largest element popped: {-heapq.heappop(max_heap)}") # Returns -2, so we negate it to get 2
print(f"Max-heap (internal) after pops: {max_heap}")

# A Priority Queue is an abstract data type that provides operations
# for inserting elements with a given priority and extracting the element
# with the highest priority.
# Heaps are the most common and efficient way to implement priority queues.

import heapq
import itertools # Used for unique entry IDs in case of equal priorities

# We forge a custom PriorityQueue class to encapsulate heap operations
# and handle more complex priority queue requirements, like stable sorting.
class PriorityQueue:
    def __init__(self):
        # We store entries as a list of [priority, entry_id, item]
        # The entry_id is a tie-breaker, ensuring stability for equal priorities.
        self._heap = []
        self._entry_finder = {}
        self._counter = itertools.count() # Unique sequence numbers for entry_id

    def push(self, item, priority):
        # If the item is already in the queue, we 'invalidate' the old entry
        # by marking it as REMOVED and insert a new one. This handles updates.
        if item in self._entry_finder:
            self.remove(item)

        count = next(self._counter)
        entry = [priority, count, item]
        self._heap.append(entry)
        self._entry_finder[item] = entry
        heapq._siftdown(self._heap, 0, len(self._heap)-1)
        # heapq.heappush internally calls _siftdown, but we use direct append
        # and _siftdown here for a slight variation that might be useful
        # if you want to inspect internal list state, but heappush is safer.
        # Let's revert to heappush for clarity and robustness:
        # heapq.heappush(self._heap, entry)

    def pop(self):
        while self._heap:
            priority, count, item = heapq.heappop(self._heap)
            if item is not self.REMOVED_SENTINEL:
                del self._entry_finder[item]
                return item, priority
        raise KeyError('pop from an empty priority queue')

    def remove(self, item):
        # Mark an existing entry as REMOVED. This doesn't physically remove it
        # from the heap until it bubbles to the top and is popped.
        # This is an efficient way to 'delete' without O(n) heap restructuring.
        entry = self._entry_finder.pop(item)
        entry[-1] = self.REMOVED_SENTINEL # Mark item as removed

    def is_empty(self):
        # A robust check for emptiness considers only active items.
        return not any(entry[-1] is not self.REMOVED_SENTINEL for entry in self._heap)

    # Sentinel value to mark removed entries
    REMOVED_SENTINEL = '<removed-item>'

# Demonstrate the custom PriorityQueue
print("\n--- Custom Priority Queue Demonstration ---")
pq = PriorityQueue()

# Push tasks with priorities
pq.push('Task A', 3) # Medium priority
pq.push('Task B', 1) # High priority
pq.push('Task C', 5) # Low priority
pq.push('Task D', 2) # Medium-high priority

print(f"Queue is empty: {pq.is_empty()}")

# Update priority of an existing task (Task A priority changes from 3 to 0)
# This demonstrates the 'remove' and 'push' pattern for updates.
pq.push('Task A', 0) # Highest priority now!

# Pop items in order of priority (lowest priority value is highest urgency)
print("\n--- Popping tasks by priority ---")
while not pq.is_empty():
    task, prio = pq.pop()
    print(f"Processing: {task} (Priority: {prio})")

print(f"Queue is empty: {pq.is_empty()}")

# --- Basic Priority Queue using tuples with heapq for simpler cases ---
print("\n--- Simple Priority Queue using heapq directly ---")
simple_pq = []
heapq.heappush(simple_pq, (3, 'Task A'))
heapq.heappush(simple_pq, (1, 'Task B'))
heapq.heappush(simple_pq, (5, 'Task C'))
heapq.heappush(simple_pq, (2, 'Task D'))

print(f"Initial simple_pq: {simple_pq}")

while simple_pq:
    priority, task = heapq.heappop(simple_pq)
    print(f"Processing (simple): {task} (Priority: {priority})")

# The heapq module offers specialized functions for more advanced heap operations.
# Understanding these unlocks greater efficiency and code elegance.

import heapq

# Initialize a heap for demonstration
initial_data = [5, 1, 8, 3, 2, 9, 4, 7]
heapq.heapify(initial_data) # Convert to a min-heap in-place
my_heap = list(initial_data) # Create a copy to show different operations
print(f"Initial heap: {my_heap}")

# 1. heappushpop(heap, item): Push an item then pop the smallest. O(log n).
# More efficient than heappush() followed by heappop() because it avoids
# one heap restructure.
print("\n--- heappushpop Demonstration ---")
value_to_add = 6
print(f"Push {value_to_add} then pop smallest from {my_heap}")
smallest_after_push = heapq.heappushpop(my_heap, value_to_add)
print(f"Popped: {smallest_after_push}, Heap: {my_heap}") # If 6 is smaller than current root, 6 is popped.
                                                      # Otherwise, current root is popped.

# Demonstrate with a smaller value pushed
my_heap = [2, 3, 4, 5, 8, 9, 7]
print(f"Current heap: {my_heap}")
value_to_add_2 = 1
print(f"Push {value_to_add_2} then pop smallest from {my_heap}")
smallest_after_push_2 = heapq.heappushpop(my_heap, value_to_add_2)
print(f"Popped: {smallest_after_push_2}, Heap: {my_heap}")

# 2. heapreplace(heap, item): Pop the smallest item, then push a new item. O(log n).
# Different from heappushpop: heapreplace pops first. Useful for fixed-size heaps (e.g., top-K).
print("\n--- heapreplace Demonstration ---")
my_heap = [1, 2, 3, 4, 5, 6, 7]
print(f"Current heap: {my_heap}")
value_to_replace = 10
print(f"Pop smallest, then push {value_to_replace} into {my_heap}")
popped_item = heapq.heapreplace(my_heap, value_to_replace)
print(f"Popped: {popped_item}, Heap: {my_heap}")

# 3. nlargest(n, iterable, key=None): Find the n largest elements. O(N log K) or O(N) if N is small.
print("\n--- nlargest Demonstration ---")
data_set = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
n_largest_elements = heapq.nlargest(3, data_set)
print(f"Original data: {data_set}")
print(f"3 largest elements: {n_largest_elements}")

# With a key function (e.g., find largest absolute values)
abs_data = [-3, 1, -4, 1, -5, 9, -2, 6, -5, 3, -5]
n_largest_abs = heapq.nlargest(3, abs_data, key=abs)
print(f"3 largest absolute values: {n_largest_abs}")

# 4. nsmallest(n, iterable, key=None): Find the n smallest elements. O(N log K) or O(N) if N is small.
print("\n--- nsmallest Demonstration ---")
n_smallest_elements = heapq.nsmallest(3, data_set)
print(f"3 smallest elements: {n_smallest_elements}")

# Heaps and Priority Queues are fundamental to solving a variety of complex problems.
# We explore two classic examples: Dijkstra's algorithm and managing event simulations.

import heapq

# --- Example 1: Dijkstra's Algorithm for Shortest Path ---
# Problem: Find the shortest path from a starting node to all other nodes
# in a weighted graph with non-negative edge weights.

def dijkstra(graph, start):
    # dist: stores the shortest distance from 'start' to each node.
    # Initialize with infinity for all nodes except 'start'.
    dist = {node: float('infinity') for node in graph}
    dist[start] = 0

    # priority_queue: stores (distance, node) tuples.
    # Using a min-heap to always extract the node with the smallest distance.
    priority_queue = [(0, start)]

    print(f"\n--- Dijkstra's Algorithm from node '{start}' ---")
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # If we found a shorter path to current_node already, skip.
        if current_distance > dist[current_node]:
            continue

        # Explore neighbors
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            # If a shorter path to neighbor is found, update distance and push to PQ.
            if distance < dist[neighbor]:
                dist[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
                print(f"  Updating path to {neighbor}: {distance}")
    return dist

# Define a sample graph (Adjacency list representation)
graph_example = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

shortest_paths = dijkstra(graph_example, 'A')
print(f"Shortest paths from A: {shortest_paths}")
# Expected: {'A': 0, 'B': 1, 'C': 3, 'D': 4}


# --- Example 2: Event Simulation / Task Scheduler ---
# Problem: Process events in chronological order, even if they arrive out of order.

def simulate_events(events):
    # Priority queue stores (timestamp, event_description)
    event_queue = []
    for timestamp, description in events:
        heapq.heappush(event_queue, (timestamp, description))

    print("\n--- Event Simulation ---")
    while event_queue:
        timestamp, description = heapq.heappop(event_queue)
        print(f"Processing event at {timestamp}: {description}")

# Sample events (can be out of order)
sample_events = [
    (10, 'User Login'),
    (3, 'System Initialization'),
    (15, 'Database Backup'),
    (5, 'Load Configuration'),
    (12, 'Process Request')
]

simulate_events(sample_events)