Find all keys smaller than x in an array min-heap

heapsort
fmunshi picture fmunshi · Oct 20, 2010 · Viewed 9.2k times · Source

Can some one describe an algorithm that finds all keys smaller than x in an array implementation of a min-heap. I want the running time to be at least O(k) where k is the number of keys reported.

I've been scratching my head for a while now with this.

Answer

Henk Holterman picture Henk Holterman · Oct 20, 2010

To get a running time of 'at least' something is not so difficult, I assume you mean 'at most'.

Unfortunately, a min-heap is not very good at finding anything else than the smallest value.

You can do a breadth-first depth-first scan of the tree-view of your heap, and terminate every branch where you have reached X. This will be O(k), but complicated.

To find all Y where Y <= X you might as well scan the entire array, this will be O(n) but with much less overhead.

The choice depends on the ratio n/k

Related questions

Quicksort vs heapsort

Both quicksort and heapsort do in-place sorting. Which is better? What are the applications and cases in which either is preferred?

Read More
Why not use heap sort always

The Heap Sort sorting algorithm seems to have a worst case complexity of O(nlogn), and uses O(1) space for the sorting operation. This seems better than most sorting algorithms. Then, why wouldn't one use Heap Sort always as a …

Read More
Why isn't heapsort stable?

I'm trying to understand why heapsort isn't stable. I've googled this, but haven't found a good, intuitive explanation. I understand the importance of stable sorting - it allows us to sort based on more than one key, which can be …

Read More