Python Tutorial: Heaps 🎯

Welcome to the Heaps tutorial! In this lesson, we'll delve into the world of Python's heapq module, which provides functions for managing heaps — efficient data structures used for various purposes like sorting, priority queues, and more. Let's get started!

What are Heaps? 📝

Heaps are specialized tree-based data structures that are either max-heaps (with the maximum element at the root) or min-heaps (with the minimum element at the root). They have several useful properties:

Complete binary tree: All levels are completely filled except possibly the last level, and all the nodes in a level are filled from left to right.
Heap property: The key at any node is either greater than or equal to (max-heap) or less than or equal to (min-heap) its children's keys.

Why are heaps useful? They allow for quick insertion, deletion, and finding the maximum or minimum element, making them suitable for applications like priority queues, dijkstra's shortest path algorithm, and more.

Working with the heapq Module 💡

The heapq module provides several functions for managing heaps in Python. The main functions are:

heapify(iterable): Converts an iterable into a heap.
heappush(heap, item): Adds an item to the heap.
heappop(): Removes and returns the smallest/largest item from the heap.
heappushpop(heap, item): Adds an item and removes the smallest/largest item from the heap.
heapreplace(heap, item): Removes and replaces the smallest/largest item with the specified item.
heappusharray(heap, array): Adds an entire array to the heap.
heappop_nlargest(heap, k): Returns the k largest items from the heap and modifies the heap accordingly.
heappush_nsmallest(heap, k): Adds k smallest items to the heap.
nlargest(n, iterable): Returns the n largest items from an iterable.
nlargest(n, iterable, key=None): Returns the n largest items from an iterable, using a custom comparison key.

Example: Priority Queue with Heaps 🎯

Let's build a simple priority queue using heaps. A priority queue is a collection of items, each with a priority associated with it. The items with the highest priority are processed first.

python

import heapq

tasks = [
    {"name": "Task1", "priority": 3},
    {"name": "Task2", "priority": 1},
    {"name": "Task3", "priority": 2},
    {"name": "Task4", "priority": 3},
]

def print_tasks(tasks):
    for task in tasks:
        print(f"Task: {task['name']}, Priority: {task['priority']}")

def build_priority_queue(tasks):
    heapq.heapify(tasks)
    return tasks

def process_next_task(tasks):
    return heapq.heappop(tasks)

def enqueue_task(tasks, task):
    heapq.heappush(tasks, task)

tasks = build_priority_queue(tasks)
print_tasks(tasks)

for i in range(len(tasks)):
    print("Processing task:")
    task = process_next_task(tasks)
    print(task)
    enqueue_task(tasks, {"name": f"New task {i+1}", "priority": i+3})

print_tasks(tasks)

In this example, we define a list of tasks, each with a name and a priority. We then create a priority queue by converting the list to a heap using heapify(). We print the initial priority queue and process the tasks one by one by using heappop() to remove the highest-priority task and print() to display it. After processing each task, we enqueue a new task with a higher priority to demonstrate adding items to the priority queue.

🚀 Challenge Time 💡

Build a program that finds the k smallest numbers and k largest numbers from an array of numbers. Use the heapq module to solve this problem.

python

# Your code here

Happy learning! 🤓🌟 If you have any questions or suggestions, feel free to leave a comment below. 💬