20250325_D&A

#timestamp 2025-03-25

heaps: k-smallest elements

add() -> for $n$ elements ( $n > k$ ):

Θ (\underset{insertion}{\underset{⏟}{k \cdot \log (k)}} + \underset{deletion}{\underset{⏟}{(n - k) \cdot \log (k)}}) = Θ (n \log k)

get() -> for $n$ elements ( $n > k$ ):

O (k \cdot 1 + k \cdot \log (k) + k \log (k)) = O (k + 2 k \log (k)) = O (k \log (k))

-> overall time

O (n \log k)

-> total memory consumption:

Θ (k)