# Complexity of finding 7th smallest element in a min-heap? [duplicate]

I don't know if it's allowed to traverse nodes in a min-heap.

Because, if traversal is allowed then for finding $$7^{th}$$ smallest element, only a constant number of nodes need to be checked, thus giving the complexity of $$\Theta(1)$$.

But if traversing is not allowed, then for finding $$7^{th}$$ smallest element, I'll need to call extract_min() 6 times, leading to a complexity of $$\Theta(\log n)$$, which I think should be correct, but not sure.

My understanding is, if I'm traversing, then it's not a min-heap, it will be an augmented min-heap. Is it correct?

• The answer depends on what you exactly mean by a min-heap. If you mean a binary heap (that is the implementation with an array) you can walk around the elements and get constant time. If however you consider min-heap as an abstract data structure (no implementation in mind) then you only have access to the extract-min operation and have logaritmic complexity. – Hendrik Jan Oct 26 '19 at 11:18
• Am I supposed to have implementation in mind when I'm talking about complexity of a certain operation involving a data structure?It will then be called an augmented data structure right? – toxicdesire Oct 26 '19 at 11:38
• @xskxzr it is not a duplicate since here we have a constant value of k – narek Bojikian Oct 26 '19 at 11:56
• @Unemployed3494 Yes, usually one has an implementation in mind when discussing complexity, heap also indicates the binary heap implementation. But heap is sometimes used for the abstract priority queue PQ. It is not unreasonable to assume the standard operations of the PQ are logaritmic (whatever implementation). If you have access to the data as in the binary heap then finding the 7th smallest number can be done directly. Don't know whether that is augmented. To me it is augmented if you keep track of the 7th element all the time, but that is just my hunch. – Hendrik Jan Oct 26 '19 at 12:08
• @hendrick, yep that's almost what I wanted to ask. If heaps are implemented as trees, then I could access tree-specific properties such as left-right-children-parent pointers etc. But that would be an augmented tree right? Why will it be a heap? How do I know what is a heap? Obviously I can't define it myself, what does the standard definition say? Or there's no such standard? – toxicdesire Oct 26 '19 at 16:21

• The time complexity for a black box min-heap is $O(\log n)$. If you are allowed to access the data structure, it is $O(1)$. – Yuval Filmus Oct 27 '19 at 11:02