Python Script for Priority Queue Using Heap Data Structure

Overview

A priority queue is a special type of queue where each element has a priority assigned to it. The element with the highest priority is served before other elements with lower priority. In Python, we can implement a priority queue using a heap data structure, which efficiently supports operations such as insert (push) and remove (pop).

Key Components

1. Heap: A binary tree where the parent node is always greater (or smaller) than its children.
2. Priority Queue Operations:
   • Enqueue (Insert an element)
   • Dequeue (Remove the highest priority element)
   • Peek (View the highest priority element without removing it)

Pseudo Code

1. Define the Heap Class

class Heap:
    initialize an empty list for heap

    function insert(value):
        append value to the end of the heap list
        heapify up from the last index

    function extract_max():
        if heap is empty:
            return None
        swap root with the last element
        remove last element
        heapify down from the root
        return the removed element

    function heapify_up(index):
        while parent index exists and parent is less than current value:
            swap parent with current value
            move to the parent's index

    function heapify_down(index):
        while children exist at index:
            find the largest child
            if largest child is greater than current value:
                swap with largest child
                move to largest child's index
            else:
                break

2. Define the Priority Queue Class

class PriorityQueue:
    initialize a Heap object

    function enqueue(value):
        call heap.insert(value)

    function dequeue():
        return call heap.extract_max()

    function peek():
        return the first element of the heap list

3. Using the Priority Queue

function main():
    create an instance of PriorityQueue
    enqueue values: 5, 1, 3, 8, 2
    print the highest priority item using peek
    while priority queue is not empty:
        print the item obtained from dequeue

Example Python Implementation

class Heap:
    def __init__(self):
        self.heap = []

    def insert(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)

    def extract_max(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return root

    def _heapify_up(self, index):
        parent_index = (index - 1) // 2
        while index > 0 and self.heap[parent_index] < self.heap[index]:
            self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
            index = parent_index
            parent_index = (index - 1) // 2

    def _heapify_down(self, index):
        largest = index
        left = 2 * index + 1
        right = 2 * index + 2
        
        if left < len(self.heap) and self.heap[left] > self.heap[largest]:
            largest = left
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right
        if largest != index:
            self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
            self._heapify_down(largest)

class PriorityQueue:
    def __init__(self):
        self.heap = Heap()

    def enqueue(self, value):
        self.heap.insert(value)

    def dequeue(self):
        return self.heap.extract_max()

    def peek(self):
        return self.heap.heap[0] if self.heap.heap else None

# Example usage
def main():
    pq = PriorityQueue()
    pq.enqueue(5)
    pq.enqueue(1)
    pq.enqueue(3)
    pq.enqueue(8)
    pq.enqueue(2)
    
    print("Highest priority item:", pq.peek())
    
    while pq.heap.heap:
        print(pq.dequeue())

main()

Conclusion

The above Python script efficiently implements a priority queue using a heap data structure. This approach provides optimal performance for enqueue and dequeue operations, making it suitable for scenarios where priority management of tasks or resources is required.