Week-13 : Correction in priority queue

Today, we discussed about implementing priority queue using ArrayList and LinkedList. While using ArrayList, we don't have to shift elements after removeMin(). I have explained a better solution below.

When we are using

Unordered ArrayList:

• add(element e) => O(1)
• peekMin() => O(n)
• removeMin() => O(n)
• Here, removeMin() requires finding the min value => O(n), removing it and then, shifting the elements will take O(n).
• A better solution: Instead of shifting, just replace the gap with the last element of the ArrayList. This can be done in constant time [O(1)].

Unordered ArrayList with index value of min:

• add(element e) => O(1)
• peekMin() => O(1)
• removeMin() => O(n)
• Again instead of shifting, replace the gap with the last element. But, we have to keep track of the index of min. To update the min index, we must traverse the list. This will take O(n) time.