timestamp 2025-03-25
heaps: k-smallest elements
asymptotic running time
- heap insertion Θ(logn)
- heap deletion Θ(logn)
- vector insertion O(1)
- vector sorting O(nlogn)1
add() -> for n elements (n>k):
Θ(insertionk⋅log(k)+deletion(n−k)⋅log(k))=Θ(nlogk)
get() -> for n elements (n>k):
O(k⋅1+k⋅log(k)+klog(k))=O(k+2klog(k))=O(klog(k))
-> overall time
O(nlogk)
asymptotic memory consumption
- max-heap size: O(k)
- vector size: O(k)
-> total memory consumption:
Θ(k)