3

So my friend and I are not seeing eye to eye in this question. It asks for the time complexity of searching for the 7th largest element in a max-heap of n elements?

I'm of the opinion that it should be O(n) and she is of the opinion it should be O(1). My logic is that suppose n is 7 then 7th largest element will be the last element in the heap so if we consider the worst case it should be O(n). She however says that since it's a max heap so finding the 7th largest element should take constant time. But using her logic even the 50th largest element or the 100th largest element can be found in O(1) time. Also the book in which we came across this question says the solution will be O(logn).

Can someone please tell me which solution is correct?

bigbong
  • 541
  • 4
  • 12

3 Answers3

6

The simple algorithm that finds the seventh-largest element in a max heap is

repeat 6 times:
    del-max(heap)
return max(heap)

The first loop performs a constant number of del-max operations, each taking O(lg n) time. The max operation takes constant time. The del-max operations dominate, leading to a total O(lg n) complexity. I'm not claiming this is optimal.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • 2
    I'm not up to speed with heaps, but don't you mean `max` instead of `min`? it sounds illogical that, after removing the six smallest elements, the new smallest is the originally 7th-*largest*... – Silly Freak Feb 06 '14 at 11:08
  • 2
    Actually it's O(k log n), where `k` is the item number. Not O(log n). – Jim Mischel Feb 06 '14 at 14:33
  • @bigbong It's covered in any good algorithms textbook and in [Wikipedia](https://en.wikipedia.org/wiki/Binary_heap#Delete). Instead of `del-max`, it can also be called `delete`, `extract-max`, etc. – Fred Foo Feb 06 '14 at 14:54
  • Oh yeah..didn't relate it to extract-max. Got it. Thanks a lot. – bigbong Feb 06 '14 at 14:59
  • Do note that doing this modifies the heap. So you're not really searching the heap for the kth largest element. Rather you're removing the first k elements from the heap. – Jim Mischel Feb 06 '14 at 15:10
  • 1
    @bigbong Thanks for the accept, but actually the other answers give better algorithms and tighter bounds. You may want to unaccept mine. – Fred Foo Feb 06 '14 at 15:37
4

There is an O(1) solution. Let's assume that the heap is represnted as a tree and max element is a root. Than the distance between the node with 7-th largest element and the root is less than or equal to 6. The number of nodes with distance to the root <= 6 is never greater than 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127. It is a constant. They can traversed in constant time.

kraskevich
  • 18,368
  • 4
  • 33
  • 45
  • To say that there's an O(1) solution is to say that you can find the kth largest element in a heap of size n in constant time, regardless of the value of k or n. What you propose is a solution that has a time complexity of O(k). – Jim Mischel Feb 06 '14 at 14:36
  • 1
    No. if k is a constant, then 2^k is O(1). – kraskevich Feb 06 '14 at 14:47
  • That's what I've mentioned above...by your logic even finding the 50th largest element will take constant time right? – bigbong Feb 06 '14 at 14:52
  • Indeed, +1. As long as `k` is constant wrt. `n`, this is O(1). – Fred Foo Feb 06 '14 at 14:56
  • Right, so I suppose an insertion sort of n items takes constant time if n is a constant. That is, I can say that I can sort an array of 100 elements in constant time using insertion sort. After all, 100 is a constant, so 100^2 is a constant. While technically correct, it's not a particularly useful thing to know. – Jim Mischel Feb 06 '14 at 14:57
  • But then it will hold true for any value of n. Even the smallest element in a max-heap will be the nth largest element of that heap. In that case we can say even finding the smallest element in a max-heap will take constant time. – bigbong Feb 06 '14 at 15:00
  • It is O(1) if k is a constant with respect to n. Finding smallest, e.m n-th element, is not a constant with respect to n. – kraskevich Feb 06 '14 at 15:02
  • So it all depends upon how we phrase our query? Let's say we have a heap of 100 elements. If i say complexity for **(n-1)th largest element** then it is `O(logn)` and if it is **99th largest element** then it is `O(1)`? – bigbong Feb 06 '14 at 15:10
  • 2
    Yes. 99th is O(1), n-1 is not. – kraskevich Feb 06 '14 at 15:15
  • @JimMischel Yes, insertion sort takes constant time for a constant number of elements, and that's **very** useful. Practical sorting algorithms exploit that fact by backing off to insertion sort for small, constant numbers of elements, while handling larger numbers of elements with quicksort or merge sort. The result is sorting in O(n lg n) time but with small coefficients. – Fred Foo Feb 06 '14 at 15:34
  • But isn't that a bit ambiguous? We are having the two different complexities for finding essentially the same element? Or is it because in such problems we consider n to be infinitely large and hence any constant term compared to n will always be small and hence constant? – bigbong Feb 07 '14 at 07:03
  • 1
    Yes. In complexity analysis, it is usually considered that n is infinitely large. – kraskevich Feb 07 '14 at 09:29
  • What will be time complexity if all elements are same ? –  Oct 24 '15 at 08:02
  • Was just guessing what will be the time complexity if we had to search f(n) th largest. We can do this by deleting f(n)-1 largest keys in O(n log n)? But what if we dont have to delete but only find? – MsA Jan 29 '18 at 19:20
3

There is an O(k) algorithm for selecting the kth element in a heap of size n, where n >> k. See An Optimal Algorithm for Selection in a Min-Heap, by Greg Frederickson.

You can download the PDF from that page (link in the upper left).

So the answer is that you, your friend, and the book you're reading are all wrong.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351