Algo Notes
  • Graphs
    • Shortest Paths
    • Union-Find
    • Minimum Spanning Trees
  • Two Pointers
  • Sliding Window
  • Stack & Queues
    • Monotonic Stack
  • Priority Queues
  • Dynamic Programming
  • Binary Indexed Tree (Fenwick Tree)
Powered by GitBook
On this page

Priority Queues

PreviousMonotonic StackNextDynamic Programming

Last updated 3 years ago

  • Heap-based implementations run at O(N log K). (K stream of N items)

    • Space: O(K)

  • Enqueue and dequeue take O(log N) time. Peeking min is O(1). (N = number of items to compare)

    • Java's PQ contain() and remove(Object) run in O(N) time.

https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/util/PriorityQueue.html