timestamp 2025-03-25

heaps: k-smallest elements

asymptotic running time

  • heap insertion
  • heap deletion
  • vector insertion
  • vector sorting 1

add() -> for elements ():

get() -> for elements ():

-> overall time

asymptotic memory consumption

  • max-heap size:
  • vector size:

-> total memory consumption:

Footnotes

  1. https://en.cppreference.com/w/cpp/algorithm/sort ↩