🔁Data Structures Unit 8 – Priority Queues and Heaps

What Are Priority Queues?

• Data structures that store and retrieve elements based on assigned priorities
• Each element has a priority value associated with it
• Higher priority elements are dequeued before lower priority elements
• Useful when elements need to be processed in a specific order determined by their importance or urgency
• Can be implemented using various underlying data structures (arrays, linked lists, heaps)
• Differ from regular queues which follow the First-In-First-Out (FIFO) principle
• Efficient for scenarios requiring quick access to the highest or lowest priority element
• Support operations like insertion (

  enqueue

  ), removal (

  dequeue

  ), and peeking at the top element

Heap Basics

• Tree-based data structure that satisfies the heap property
• Heap property ensures the root node has the highest (max-heap) or lowest (min-heap) priority
• Complete binary tree structure
  • All levels are fully filled except possibly the last level
  • Nodes in the last level are filled from left to right
• Stored in an array representation for efficient memory utilization
• Parent-child relationship
  • For a node at index

    i

    , its parent is at index

    (i-1) // 2

  • Left child is at index

    2i + 1

    , right child is at index

    2i + 2

• Heapify process maintains the heap property after insertions or deletions

Types of Heaps

• Max-Heap
  • Parent node has a higher priority (larger value) than its children
  • Root node contains the maximum element
  • Useful for finding the maximum value efficiently
• Min-Heap
  • Parent node has a lower priority (smaller value) than its children
  • Root node contains the minimum element
  • Useful for finding the minimum value efficiently
• Binary Heap
  • Each node has at most two children
  • Commonly used to implement priority queues
• Fibonacci Heap
  • More advanced heap structure with improved amortized time complexity for certain operations
  • Consists of a collection of trees with specific properties

Heap Operations

• Insertion (

  insert

  or

  push

  )
  • Adds a new element to the heap
  • Element is initially added to the end of the heap
  • Sift-up (percolate-up) operation is performed to restore the heap property
    • Compares the inserted element with its parent and swaps if necessary
    • Continues until the heap property is satisfied
• Deletion (

  delete

  or

  pop

  )
  • Removes the root element (highest priority) from the heap
  • Last element in the heap is moved to the root position
  • Sift-down (percolate-down) operation is performed to restore the heap property
    • Compares the root element with its children and swaps with the higher priority child
    • Continues until the heap property is satisfied
• Peeking (

  peek

  or

  top

  )
  • Retrieves the root element without removing it from the heap
• Heapify
  • Converts an array into a valid heap structure
  • Performed in linear time complexity

Implementing Priority Queues with Heaps

• Priority queues can be efficiently implemented using heaps
• Heap structure ensures the highest (or lowest) priority element is always at the root
• Insertion operation
  • Add the element to the end of the heap
  • Perform sift-up to restore the heap property
  • Time complexity: O(log n)
• Removal operation
  • Remove the root element (highest priority)
  • Move the last element to the root position
  • Perform sift-down to restore the heap property
  • Time complexity: O(log n)
• Peeking operation
  • Return the root element without removing it
  • Time complexity: O(1)
• Heaps provide an efficient way to maintain the priority order of elements

Time Complexity Analysis

• Insertion (enqueue)
  • Sift-up operation has a time complexity of O(log n)
  • In the worst case, the new element may need to be swapped with its parent up to the root level
• Deletion (dequeue)
  • Sift-down operation has a time complexity of O(log n)
  • In the worst case, the root element may need to be swapped with its children down to the leaf level
• Peeking (top)
  • Accessing the root element has a time complexity of O(1)
  • No traversal or comparisons are required
• Building a heap from an array (heapify)
  • Has a time complexity of O(n)
  • Performed by starting from the last non-leaf node and applying sift-down for each node
• Heaps provide logarithmic time complexity for insertion and deletion operations

Real-World Applications

• Task Scheduling
  • Priority queues can be used to schedule tasks based on their priority or deadline
  • Highest priority tasks are processed first
• Dijkstra's Shortest Path Algorithm
  • Priority queue is used to efficiently select the vertex with the minimum distance
  • Helps in finding the shortest path in a weighted graph
• Huffman Coding
  • Priority queue is used to build the Huffman tree for data compression
  • Characters with higher frequencies are assigned shorter bit representations
• Event-Driven Simulations
  • Priority queue manages events based on their timestamp
  • Events with the earliest timestamp are processed first
• Operating System Process Scheduling
  • Priority queue determines which process to execute next based on priority
  • Ensures efficient utilization of system resources

Practice Problems and Coding Exercises

• Implement a max-heap and min-heap from scratch
• Solve the "Kth Largest Element in an Array" problem using a heap
• Implement a priority queue using a binary heap
• Given a list of tasks with priorities and deadlines, schedule them using a priority queue
• Implement Dijkstra's shortest path algorithm using a priority queue
• Design a system for managing customer support tickets based on priority
• Solve the "Merge K Sorted Lists" problem using a priority queue
• Implement a heap sort algorithm to sort an array in ascending or descending order