New answers tagged heaps
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
