Priority Queues1.4. Naive Two-Dimensional Structure for Priority Queues

Try these first

1. 1.

   What is a priority queue?

   Hint

   Think about how tasks are sorted in importance.

2. 2.

   What two operations do we perform on a priority queue?

   Hint

   Consider what happens when a new job arrives.

3. 3.

   What is the time complexity for inserting a job into an unsorted list?

   • O(1)
   • O(N)
   • O(log N)

   Hint

   Think about how we add jobs.

4. 4.

   True or False: In a sorted list, the maximum element is always at the beginning.

   • True
   • False

   Hint

   Consider how elements are ordered.

5. 5.

   Given a priority queue with the following tasks and their priorities: (A, 3), (B, 5), (C, 2). Insert them into a two-dimensional structure. Then, delete the max and show the state of the structure.

   Hint

   Remember how to determine the correct row and position for each insertion.

6. 6.

   Critically analyze the efficiency of your two-dimensional structure for 100 jobs, state the impacts of the algorithmic complexity on performance and how it compares with heaps.

   Hint

   Think about the trade-offs in performance and the practical applications of each structure.