New answers tagged


First note that $\text{increase-key}$ must be $O(\log n)$ if we wish for $\text{insert}$ and $\text{find-min}$ to stay $O(1)$ as they are in a Fibonacci heap. If it weren't you'd be able to sort in $O(n)$ time by doing $n$ $\text{insert}$s, followed by repeatedly using $\text{find-min}$ to get the minimum and then $\text{increase-key}$ on the head by $\...


There's a O(K) Algorithm mentioned in the below link.


It can be done in O(klogk) time when k is the kth smallest element lets say we have an arbitrary min heap - H1 with n elements in order to find the kth smallest element in this heap, we need an additional heap - H2 -we assume that every element in H2 points at the matching element in H1 so we have O(1) access to the element's children(2.1) the ...


None of the answers is correct. It is $O(\min(k \log n, n))$. If $k < n/\log n$ then doing $k$ pops and checking the minimal element is fastest, otherwise a scan through the whole heap is faster.


This is not possible. If this is the case then we could extract a sorted list in linear time; $O(1)$ for each $k$th smallest element. We can also create a min heap in linear time thus we could sort in linear time! We know comparison sorting has an $\Omega(n \log n)$ lower bound worst case, so this is not possible.

Top 50 recent answers are included