Heap & Priority Queue

Heap Data Structure

A Heap is a complete binary tree that satisfies the heap property:

• Max-Heap: The value of each node is greater than or equal to the values of its children.
• Min-Heap: The value of each node is less than or equal to the values of its children.

Heaps are used to implement priority queues, where insertion, deletion, and access to the highest (or lowest) priority element are efficient.

Key Operations

• Insertion: Add an element to the heap and restore heap property by “bubbling up”.
• Deletion: Remove the root element and restore heap property by “heapifying” down.

Python Example: Max-Heap Insertion & Deletion

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[l] > arr[largest]:
        largest = l

    if r < n and arr[r] > arr[largest]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def insert(arr, newNum):
    arr.append(newNum)
    current = len(arr) - 1
    while current > 0:
        parent = (current - 1) // 2
        if arr[current] > arr[parent]:
            arr[current], arr[parent] = arr[parent], arr[current]
            current = parent
        else:
            break

def deleteNode(arr, num):
    size = len(arr)
    i = 0
    for i in range(size):
        if arr[i] == num:
            break
    arr[i], arr[-1] = arr[-1], arr[i]
    arr.pop()
    if i < len(arr):
        heapify(arr, len(arr), i)

# Usage
arr = []
insert(arr, 3)
insert(arr, 4)
insert(arr, 9)
insert(arr, 5)
insert(arr, 2)

print("Max-Heap array:", arr)

deleteNode(arr, 4)
print("After deleting an element:", arr)

Priority Queue

A Priority Queue is an abstract data structure where each element is associated with a priority. Elements with higher priority are served before those with lower priority.

Heaps are commonly used to implement priority queues efficiently.

Python Example using heapq module

import heapq

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

    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, item))

    def pop(self):
        if self.heap:
            return heapq.heappop(self.heap)[1]
        else:
            return None

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

# Usage Example
pq = PriorityQueue()
pq.push("task1", 3)
pq.push("task2", 1)
pq.push("task3", 2)

print(pq.pop())  # Outputs: task2 (highest priority)
print(pq.peek()) # Outputs: task3

Applications

• Task Scheduling in operating systems.
• Dijkstra's shortest path algorithm uses priority queues.
• CPU scheduling and bandwidth management.