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?

  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Oct 26 '19 at 11:18
  • $\begingroup$ 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? $\endgroup$ – toxicdesire Oct 26 '19 at 11:38
  • $\begingroup$ @xskxzr it is not a duplicate since here we have a constant value of k $\endgroup$ – narek Bojikian Oct 26 '19 at 11:56
  • $\begingroup$ @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. $\endgroup$ – Hendrik Jan Oct 26 '19 at 12:08
  • $\begingroup$ @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? $\endgroup$ – toxicdesire Oct 26 '19 at 16:21

If you had a "black-box" min heap where the only operations available to you are adding elements and extracting (reading and simultaneously removing) the smallest item, then the time complexity is O (n) obviously.

It is imaginable that you have a specific implementation where even finding the second smallest element cannot be done in constant time. You might have in your data structure O (log n) items that might be the second smallest, and the O (log n) operation to remove the smallest item will also determine the second largest. I find it hard to describe an algorithm that works that way, but I'm sure it's possible.

The way a min-heap is usually implemented (or the way it is implemented if I had to implement it, or the way it is implemented in a random text book), finding the 7th smallest element can be done in constant time.

| cite | improve this answer | |
  • $\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Oct 27 '19 at 11:02
  • $\begingroup$ @Yuval, so are we allowed to access the data structure in general? Does it not become augmented if we do that? $\endgroup$ – toxicdesire Oct 27 '19 at 12:12
  • $\begingroup$ I'm not sure what you mean by "allowed". If you're trying to solve some problem, and an efficient solution requires you to look under the hood, then it might or might not be feasible, depending on practical software engineering considerations. The efficient algorithm in this case doesn't require any augmentation, it just requires looking under the hood. $\endgroup$ – Yuval Filmus Oct 27 '19 at 12:40
  • $\begingroup$ By allowed, I mean theoretically. Does the definition of a min-heap allow us to do that? Is there any standard definition for this that the world/academia agrees on or there's no such thing? $\endgroup$ – toxicdesire Oct 27 '19 at 14:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.