06 - Priority Queues

Introduction to Priority Queues

  • Background materials from Robert Sedgewick and Kevin Wayne, relating to data structures and algorithms.

  • Topics Covered:

    • API and elementary implementations

    • Binary heaps

    • Heapsort

    • Event-driven simulation

Priority Queues Overview

  • Definition: A priority queue is a data structure enabling efficient insertion and deletion of items based on assigned priorities.

  • Key Operations:

    • Insertion (INSERT)

    • Deletion of the maximum or minimum item (DELETE-MAX or DELETE-MIN)

Collections Data Type

  • Basic Data Structures:

    • Stack: Push and Pop operations using a linked list or resizing array.

    • Queue: Enqueue and Dequeue operations also supported by linked lists or resizing arrays.

    • Priority Queue: Insert and Delete-Max operations typically implemented using binary heaps.

    • Symbol Table: PUT, GET, DELETE operations utilizing binary search tree or hash table.

    • Set: ADD, CONTAINS, DELETE operations implemented by binary search tree or hash table.

Characteristics of Priority Queues

  • Comparison to Other Data Structures:

    • Stack: Pops the most recently added item.

    • Queue: Pops the least recently added item.

    • Randomized Queue: Pops a random item.

    • Priority Queue: Pops the largest or smallest item depending on configuration.

  • Generalization: The priority queue generalizes the functionality of other data structures, providing versatile control over item retrieval based on priority.

API Requirements for Priority Queues

  • Type Constraints: Keys in a priority queue must be generic and comparable (Comparable interface).

  • API Methods:

    1. MaxPQ() - Create an empty priority queue.

    2. MaxPQ(Key[] a) - Create a priority queue with initial keys.

    3. void insert(Key v) - Insert a key into the queue.

    4. Key delMax() - Return and remove the largest key.

    5. boolean isEmpty() - Check if the queue is empty.

    6. Key max() - Retrieve the largest key without removing it.

    7. int size() - Get the current number of entries in the queue.

Applications of Priority Queues

  • Event-driven Simulation (example: customers in line, particle collisions)

  • Numerical Computation (example: reducing roundoff error)

  • Discrete Optimization (examples: bin packing, scheduling)

  • Artificial Intelligence (examples: A* search)

  • Computer Networks (web caching)

  • Data Compression (example: Huffman codes)

  • Operating Systems (load balancing, interrupt handling)

  • Graph Searching (Dijkstra’s and Prim’s algorithms)

  • Number Theory (sum of powers)

  • Spam Filtering (Bayesian filters)

  • Statistics (online median in data streams)

Challenges with Priority Queues

  • Finding Largest m Items in n Stream: Example use case for monetary fraud detection and monitoring suspicious documents.

  • Memory Constraints: Not enough memory to store n items requires efficient management.

  • Implementation Example:

    MinPQ<Double> pq = new MinPQ<Double>();
while (StdIn.isEmpty()) {
    double value = StdIn.readDouble();
    pq.insert(value);
    if (pq.size() > m) pq.delMin();
}
// Now pq contains the largest m numbers

Running Times for Different Implementations

  • Time Complexity:

    • Sorting: O(n log n)

    • Elementary PQ: O(m n)

    • Binary Heap: O(n log m)

  • Understanding of time complexities crucial for practical applications, especially when scaling with large datasets.

Priority Queue Implementations

Elementary Implementations using Arrays

  • Operations on Unordered Arrays:

    • Insertion: O(1)

    • Remove Max: O(n)

  • Operations on Ordered Arrays:

    • Insertion: O(n)

    • Remove Max: O(1)

Binary Heap Structure

  • Concept: Array representation of a complete binary tree where:

    • Parents must have a higher key than their children (max-heap)

    • Children of a node can be accessed via simple calculations using their indices.

Insertion and Deletion Management

  • Insert Operation:

    1. Add node at the end of the array.

    2. Use swim operation to maintain heap order.

  • Delete Maximum Operation:

    1. Swap the root with the last node.

    2. Use sink operation to reestablish heap invariant.

Conclusion

  • Understanding priority queues, their operations, and efficient implementations are key in data structure algorithms.

  • Applications span numerous fields, showcasing the importance of mastering this data structure.