Priority queue with heaps in Data Structures Theory - Mini Project: Build & Apply

Priority queue with heaps

📖 Scenario: You are managing tasks with different importance levels. You want to organize them so the most important task is always easy to find and remove.

🎯 Goal: Build a simple priority queue using a heap structure to keep tasks sorted by their priority.

📋 What You'll Learn

Create a list of tasks with their priorities

Set a variable for the heap size

Use a loop to build the heap from the tasks

Add the final step to maintain the heap property after removing the top task

💡 Why This Matters

🌍 Real World

Priority queues are used in scheduling tasks, managing resources, and handling events where some items must be processed before others.

💼 Career

Understanding priority queues and heaps is important for software developers, data engineers, and anyone working with algorithms that require efficient sorting and retrieval.

1

Create the initial list of tasks with priorities

Create a list called tasks with these exact tuples: (3, 'Wash dishes'), (1, 'Pay bills'), (4, 'Do homework'), (2, 'Clean room').

Data Structures Theory

# Create the list called tasks with the given tuples
# Your code here

Need a hint?

Use a list with tuples where the first value is priority and the second is the task name.

2

Set the heap size variable

Create a variable called heap_size and set it to the length of the tasks list.

Data Structures Theory

tasks = [(3, 'Wash dishes'), (1, 'Pay bills'), (4, 'Do homework'), (2, 'Clean room')]
# Set heap_size to the length of tasks
# Your code here

Need a hint?

Use the len() function to get the number of tasks.

3

Build the heap from the tasks list

Write a for loop with variable i that goes from heap_size // 2 - 1 down to 0 (inclusive). Inside the loop, call a function heapify(tasks, heap_size, i) to build the heap.

Data Structures Theory

tasks = [(3, 'Wash dishes'), (1, 'Pay bills'), (4, 'Do homework'), (2, 'Clean room')]
heap_size = len(tasks)

def heapify(tasks, heap_size, i):
    # This function will be defined later
    pass

# Build the heap using a for loop
# Your code here

Need a hint?

Use a reverse range loop and call heapify inside it.

4

Complete the heapify function to maintain heap property

Complete the heapify function to maintain the max-heap property. Use variables largest, left, and right to compare priorities and swap tasks if needed. Remember to call heapify recursively if a swap happens.

Data Structures Theory

tasks = [(3, 'Wash dishes'), (1, 'Pay bills'), (4, 'Do homework'), (2, 'Clean room')]
heap_size = len(tasks)

def heapify(tasks, heap_size, i):
    # Complete the heapify function here
    # Your code here

for i in range(heap_size // 2 - 1, -1, -1):
    heapify(tasks, heap_size, i)

Need a hint?

Compare the priority values at left and right with largest. Swap if needed and call heapify again.