2nd largest element of a max-heap

bfs
data-structure
doubt
heaps

#1

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


#2

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.


#3

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.


#4

Thanks a lot!!


#5

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?


#6

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


#7

@bipin2 Yes you can do that.


#8

Sorry…I forget that…:slight_smile: