Module $10$ Homework $-$ Priority Queue

Implementation for Task Management

Overview

We will implement a priority queue to manage the scheduling of tasks in an operating system. Tasks with

higher priority should be executed first. You are provided with a skeleton code for three classes Entry,

MaxHeap, and TaskManager. You will complete the implementation of the Entry class and MaxHeap class.

Requirements:

$1.$ Entry Class Implementation:

Implement the comparison methods in the provided Entry class to compare entries based on

priority.

$2.$ MaxHeap Class Implementation:

Implement methods to insert entries, remove the maximum priority entry, maintain the heap

property, and change the priority of existing tasks.

Implement heapifying methods to ensure the heap property is maintained after insertion,

removal, and priority change operations.

$3.$ TaskManager Class Implementation:

The TaskManager class includes methods to add tasks, remove tasks with the highest priority.

Use the MaxHeap class methods to manage the task queue efficiently.

Examples

Several examples of behavior shown below.

# Creating entries

entry$1=$ Entry$($priority$=5,$ process$\_$id$=$"Process $1")$

entry$2=$ Entry$($priority$=3,$ process$\_$id$=$"Process $2")$

entry$3=$ Entry$($priority$=7,$ process$\_$id$=$"Process $3")$

entry$4=$ Entry$($priority$=8,$ process$\_$id$=$"Process $4")$

entry$5=$ Entry$($priority$=2,$ process$\_$id$=$"Process $5")$

entry$6=$ Entry$($priority$=6,$ process$\_$id$=$"Process $6")$

entry$7=$ Entry$($priority$=4,$ process$\_$id$=$"Process $7")$

# Initializing MaxHeap

max$\_$heap $=$ MaxHeap$()$

# Adding entries to the max heap

max$\_$heap.put$($entry$1)$

max$\_$heap.put$($entry$2)$

max$\_$heap.put$($entry$3)$

max$\_$heap.put$($entry$4)$

hw$10.$md $2024-04-11$

$2/2$

max$\_$heap.put$($entry$5)$

max$\_$heap.put$($entry$6)$

max$\_$heap.put$($entry$7)$

# Changing priority of a process

max$\_$heap.change$\_$priority$($process$\_$id$=$"Process $1",$ new$\_$priority$=10)$

# Changing priority of a process

max$\_$heap.change$\_$priority$($process$\_$id$=$"Process $3",$ new$\_$priority$=1)$

# Removing processes until heap is empty

while max$\_$heap:

print$($f$"$Removing max priority process: $\{$max$\_$heap.remove$\_$max$()\}")$

# Expected output:

# Removing max priority process: Process $1$

# Removing max priority process: Process $4$

# Removing max priority process: Process $6$

# Removing max priority process: Process $7$

# Removing max priority process: Process $2$

# Removing max priority process: Process $5$

# Removing max priority process: Process $3$

Starter Code:

class Entry:

$"""$Represents an entry in the priority queue."""

def $\_\_$init$\_\_($self$,$ priority, process$\_$id$)$:

$"""$Initializes an Entry object with a given priority and process ID$."""$

self.priority $=$ priority

self.process$\_$id $=$ process$\_$id

def $\_\_$repr$\_\_($self$)$:

$"""$Returns a string representation of the Entry object."""

return f$"$Entry$($priority$=\{$self$.$priority$\},$ process$\_$id$=\{$self$.$process$\_$id$\})"$

####### Implement all Entry class methods under this line #######

def $\_\_$gt$\_\_($self$,$ other$)$:

$"""$Compares the priority of this entry with another entry.

Returns:bool: True if this entry has higher priority than the other, False otherwise."""

def $\_\_$eq$\_\_($self$,$ other$)$:

$"""$Checks if this entry is equal to another entry based on priority.

Returns:bool: True if the priorities are equal, False otherwise."""

class MaxHeap:

$"""$Represents a max heap data structure."""

def $\_\_$init$\_\_($self$)$:

$"""$Initializes a MaxHeap object."""

self.$\_$heap $=[]$

####### Implement all MaxHeap class methods under this line #######

def put$($self$,$ entry$)$:

$"""$Inserts an entry into the max heap."""

def remove$\_$max$($self$)$:

$"""$Removes and returns the entry with the maximum priority from the max heap.

Returns:The process ID that was removed from the queue. raise IndexError if the heap is empty"""

def change$\_$priority$($self$,$ process$\_$id$,$ new$\_$priority$)$:

$"""$Changes the priority of a process in the max heap.

Returns:bool: True if the priority change was successful, False otherwise."""

def $\_$upheap$($self$,$ index$)$:

$"""$Performs up$-$heap operation to maintain heap property after insertion."""

def $\_$downheap$($self$,$ index$)$:

$"""$Performs down$-$heap operation to maintain heap property after removal."""

def $\_\_$len$\_\_($self$)$:

$"""$len is number of items in PQ$"""$

class TaskManager:

$"""$Manages the execution of processes using a priority queue."""

def $\_\_$init$\_\_($self$)$:

$"""$Initializes a TaskManager object."""

self.processor$\_$queue $=$ MaxHeap$()$

####### Implement all TaskManager class methods under this line #######

def add$\_$process$($self$,$ entry$)$:

$"""$Adds a process to the processor queue."""

def remove$\_$process$($self$)$:

$"""$Removes and returns the process with the highest priority from the processor queue."""