10.5.1. Priority Queue Implementation

Try these first

1. 1.

   What is the main property of a max heap?

   Hint

   Consider the relationship between parents and children.

2. 2.

   How can you determine the children of a node at index 2 in an array representation of a heap?

   Hint

   Use the formulas: left child index = 2i + 1 and right child index = 2i + 2.

3. 3.

   What is the time complexity of inserting an element in a max heap?

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

   Hint

   Recall how insertion works in relation to the height of a tree.

4. 4.

   True or False: In a min heap, the highest value is always at the root.

   • True
   • False

   Hint

   Think about the properties of heaps.

5. 5.

   Given the array [12, 7, 5, 29, 38, 3], create a max heap and explain your process.

   Hint

   Map out each path as you fix the heap.

6. 6.

   Consider an application using priority queues in scheduling tasks. Discuss how a heap could help manage this effectively.

   Hint

   Think about the properties of priorities in daily tasks.