Removing 2nd smallest element from a binary Max-Heap

Question

This question is similar to this. The difference is that I have a binary Max-Heap instead of a Min-Heap. Which makes the question totally different.

My thoughts:

1) I go through all the nodes to find the second smallest element, this will take O(n)

2) When I find the 2nd smallest element, I bubble that element up, by swapping it with its parent until it reaches the root, this will take O(logn)

3) I remove the element from the root and take the right-most element and store it at root location (regular heap delete operation), this will take O(logn)

Total will be O(n) + O(logn) + O(logn), which is O(n).

Edited: Added binary

Is there a better solution than that?

Why not just use a min heap? Any efficient solution for this would indirectly create a min heap anyways. — ElKamina, May 09 '12 at 15:23
@ElKamina; This is a question (not homework) that I'm interested in knowing the answer to. — Roronoa Zoro, May 09 '12 at 15:25
I am assuming that by "heap" you are referring to a [binary heap](http://en.wikipedia.org/wiki/Binary_heap) - is that correct? — amit, May 09 '12 at 15:26

score 1 · Answer 1 · answered Jul 10 '12 at 12:33

1

Why don't you keep a small array, with 2 elements, to keep a copy of the smallest 2 elements?

Then, all operations are only altered with O(1) steps and you can provide the answer in constant time.

answered Jul 10 '12 at 12:33

Churrupipi

11
1

hhsaffar · Answer 2 · 2012-05-09T15:40:51.123

The second smallest element is either a leaf or parent of a leaf and the leaf is the only child of it.

How to remove the second smallest element:

Find it by searching through leaves and possibly the father that has only one child. O(n)
If the 2nd smallest element is parent of a node, the node must be the smallest element and should be the right most leaf. Replace the 2nd smallest with its child and it is over. O(1)
If the 2nd smallest element is a leaf, replace it with the right most leaf in the deepest level and bubble up. O(log(n))

So it is O(n)+O(log(n)) which is still O(n) but with fewer comparisons.

amit · Answer 3 · 2012-05-09T15:40:21.320

When it comes to big O notation - no, it cannot be done better. Finding an arbitrary element in a max heap is O(n).

You could however reduce the number of maximum nodes you need to traverse to 1/2 * n, and essentially double the speed of the algorithm. [still O(n) domain], since the 2nd smallest element in a max heap has at most one son, so you can traverse only leaves (n/2 of those), and one element at most which has only one son. (remember, a binary heap is an array representing a complete tree, thus at most one element has exactly one son).

One can also enhance a bit the removal step, but I doubt it will have any significant affect), so I wouldn't bother putting effort into it.

Removing 2nd smallest element from a binary Max-Heap

3 Answers3