Data Structures & Algorithms in Swift · Priority Queue |

This is a companion discussion topic for the original entry at

Hi @catie & @jessycatterwaul,
Q: I would like to understand how Heap’s Dequeueing has a constant cost.
A: (I think) It’s also O(log n) as we are trying to remove the root which is 3 steps:

  1. Swap array’s 0 with (count - 1) : O(1)
  2. RemoveLast() from Array : O(1)
  3. SiftDown(index: 0) : O(log n)

Please correct me if I am wrong & Thanks for the great video tutorial on DS & Algo.


1 Like

Great catch! You are correct; it was our error.

Thanks @jessycatterwaul for clarifying.