New answers tagged

4

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 $\...


0

There's a O(K) Algorithm mentioned in the below link. https://www.sciencedirect.com/science/article/pii/S0890540183710308


0

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 ...


0

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.


1

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