Priority Queue Introduction 🎯

Welcome to the exciting world of Data Structures and Algorithms! Today, we're going to dive into a fascinating concept called Priority Queue. Let's embark on this journey together! 🚀

What is a Priority Queue? 📝

A Priority Queue is a special type of data structure that stores elements in a way that prioritizes them according to a specific rule. Each element has a priority associated with it, and elements with higher priority are served before the ones with lower priority.

Why Priority Queue? 💡

Priority Queues are incredibly useful in various real-life scenarios. For instance, they are used in scheduling processes in Operating Systems, managing tasks in project management tools, and even in game development for pathfinding algorithms.

Types of Priority Queues 📝

There are mainly two types of Priority Queues:

Max Heap Priority Queue
Min Heap Priority Queue

Max Heap Priority Queue 📝

A Max Heap is a complete binary tree where each parent is greater than or equal to its children. In a Max Heap Priority Queue, the highest priority element is always at the root.

Min Heap Priority Queue 📝

A Min Heap is a complete binary tree where each parent is less than or equal to its children. In a Min Heap Priority Queue, the lowest priority element is always at the root.

Implementing a Priority Queue 💡

Let's write a simple implementation of a Max Heap Priority Queue in Python:

python

class PriorityQueue:
    def __init__(self):
        self.data = []

    def insert(self, data):
        self.data.append(data)
        self._swim(len(self.data) - 1)

    def _swim(self, k):
        while k > 1 and self._larger_child(k):
            self._swap(k // 2, k)
            k = k // 2

    def _larger_child(self, k):
        return k * 2 > len(self.data) or self.data[k * 2] > self.data[k * 2 + 1]

    def _swap(self, i, j):
        self.data[i], self.data[j] = self.data[j], self.data[i]

    def delete(self):
        max_val = self.data[1]
        last_val = self.data.pop()
        if len(self.data) > 0:
            self.data[1] = last_val
            self._sink(1)
        return max_val

    def _sink(self, k):
        while True:
            l = 2 * k
            r = l + 1
            largest = l
            if r <= len(self.data) and self.data[r] > self.data[l]:
                largest = r
            if largest > len(self.data) or self.data[largest] >= self.data[k]:
                break
            self._swap(k, largest)
            k = largest

    def __repr__(self):
        return str(self.data)

if __name__ == "__main__":
    pq = PriorityQueue()
    pq.insert(2)
    pq.insert(5)
    pq.insert(1)
    print(pq)  # Output: [1, 5, 2]
    print(pq.delete())  # Output: 1
    print(pq)  # Output: [5, 2]

Quiz 🎯

We hope you enjoyed learning about Priority Queues! Stay tuned for more exciting concepts in the world of Data Structures and Algorithms. Happy coding! 🚀💻