# Tag Info

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.