You are not logged in. Please login at www.codechef.com to post your questions!

×

2nd largest element of a max-heap

Hai i have just started learning Data Structures.Please help me...

Suppose i have a max heap of arr[1....n].arr[1] stores the maximum element. Is there any way in which i can find the second largest element in the array. we are not supposed to change the heap

asked 29 Mar '14, 23:54

bipin2's gravatar image

3★bipin2
3.1k254671
accept rate: 8%

edited 29 Mar '14, 23:55


The max-heap is a tree structure in which the root contains the maximum element and value of each node is greater than the value of its children. The max-heap is stored as an array. So as the first element or the first index stores the maximum element of the max-heap. The second largest element of the heap is either of the two children of the max node i.e. either node 2 or node 3. Check the one which is bigger.

link

answered 30 Mar '14, 00:11

vermashubhang's gravatar image

5★vermashubhang
1.5k11025
accept rate: 23%

Thanks a lot!!

(30 Mar '14, 22:01) bipin23★
1

@bipin2 Your welcome! Please accept the solution if you are satisfied so that the question could be closed.

(31 Mar '14, 14:02) vermashubhang5★

Sorry....I forget that..:)

(01 Apr '14, 19:14) bipin23★

If you are using a priority_queue , this can be done very easily.

  1. Pop from priority_queue and store it in a temp variable.(This the largest element in the heap).
  2. Pop again from the queue which will be the second largest of the max_heap.
  3. Push again the temp variable into the heap, so that the heap remains in its initial state and only the second most largest element is removed from the heap.

If you need more clarifications just leave a comment below.

link

answered 30 Mar '14, 00:24

alphaparticle's gravatar image

4★alphaparticle
151411
accept rate: 25%

thanks....but i wanted to the array to remain the same....or we can take 2 temporary variables and the pop and pop and then push back the 2 temporary variables right?

(30 Mar '14, 22:03) bipin23★

@bipin2 Yes you can do that.

(01 Apr '14, 00:29) alphaparticle4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,310
×461
×288
×42

question asked: 29 Mar '14, 23:54

question was seen: 6,659 times

last updated: 01 Apr '14, 19:14