Data Structures & Algorithms in Swift · Priority Queue | raywenderlich.com

🎓 Courses & Articles
1
This is a companion discussion topic for the original entry at https://www.raywenderlich.com/977854-data-structures-algorithms-in-swift/lessons/18
2

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.

Cheers
MK

1 Like
3

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

4

Thanks @jessycatterwaul for clarifying.

Cheers
MK