ISRO2018-57

Question

ISRO2018-57

Arjun asked Apr 22, 2018 • recategorized Dec 9, 2022 by Lakshman Bhaiya

15,118 views

See all

ankitgupta.1729

commented Jan 4, 2020

@`JEET

Can you tell me how you are getting 14,13,8,12,10.

Here, , in questiont is not given which 2 elements we have to delete in binary max-heap. I am assuming that we have to delete first 2 maximum elements one by one.

In max-heap or min-heap, to delete target element, first we have to swap, target element with last element and then delete the last element but in this procedure property of max-heap or min-heap may violate. So, we have to fix it by using max-heapify or min-heapify.

1) To delete 25,

-- first swap 25 with last element in the array i.e. 12

-- delete 25

-- Apply max-heapify.

Then do the same procedure for next maximum element.

2 Answers

See all

Related questions

Deprecated: Implicit conversion from float-string "1524410572.452" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1524410572.452" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1524410572.452" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1524410572.452" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1524410568.202" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1524410568.202" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1524410568.202" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1524410568.202" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1524410567.699" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1524410567.699" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1524410567.699" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1524410567.699" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1524410588.991" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1524410588.991" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1524410588.991" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1524410588.991" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

3.8k

views

3 answers

2 votes

Arjun asked Apr 22, 2018

3,788 views

ISRO2018-63

Consider a singly linked list of the form where $F$ is a pointer to the first element in the linked list and $L$ is the pointer to the last element in the list. The time ...

Arjun

3.8k views

Arjun asked Apr 22, 2018

28.6k

views

2 answers

3 votes

Arjun asked Apr 22, 2018

28,586 views

ISRO2018-79

A doubly linked list is declared as:struct Node { int Value; struct Node *Fwd; struct Node *Bwd; };Where Fwd and Bwd represent forward and backward link to the adjacent e...

Arjun

28.6k views

Arjun asked Apr 22, 2018

6.4k

views

4 answers

2 votes

Arjun asked Apr 22, 2018

6,431 views

ISRO2018-80

If $\text{Tree-1}$ and $\text{Tree-2}$ are the trees indicated below:Which traversals of $\text{Tree-1}$ and $\text{Tree-2}$, respectively, will produce the same sequence...

Arjun

6.4k views

Arjun asked Apr 22, 2018

8.5k

views

2 answers

5 votes

Arjun asked Apr 22, 2018

8,540 views

ISRO2018-1

Consider the following program{ int x=1; printf("%d",(*char(char*)&x)); }Assuming required header files are included and if the machine in which this program is executed ...

Arjun

8.5k views

Arjun asked Apr 22, 2018

@`JEET

Can you tell me how you are getting 14,13,8,12,10.

Here, , in questiont is not given which 2 elements we have to delete in binary max-heap. I am assuming that we have to delete first 2 maximum elements one by one.

In max-heap or min-heap, to delete target element, first we have to swap, target element with last element and then delete the last element but in this procedure property of max-heap or min-heap may violate. So, we have to fix it by using max-heapify or min-heapify.

1) To delete 25,

-- first swap 25 with last element in the array i.e. 12

-- delete 25

-- Apply max-heapify.

Then do the same procedure for next maximum element. — ankitgupta.1729, Jan 4, 2020
@`JEET if we delete 25, which is the 1st element in the array, like this way, we have to shift all the elements in the left to maintain the heap structure and decrease the heap-size by 1 then only we can apply max-heapify.. right ? and shifting all remaining elements will take worst case O(n) time. right ? — ankitgupta.1729, Jan 4, 2020
But it is not technically incorrect?

Can you please show your method? — `JEET, Jan 4, 2020
Here, binary max-heap is represented as an array whose elements are : 25,14,16,13,10,8,12.

1) delete 25 :

first swap 25 and 12. So, array becomes : 12,14,16,13,10,8,25.

Now, delete 25 and decrease heap-size by 1. So, array becomes : 12,14,16,13,10,8

Now, apply max-heapify on it. So, array representation after max-heapify becomes : 16,14,12,13,10,8.

2) delete 16 :

first swap 16 and 8. So, array becomes : 8,14,12,13,10,16.

Now, delete 16 and decrease heap-size by 1. So, array becomes : 8,14,12,13,10.

Now, apply max-heapify on it. So, array representation after max-heapify becomes : 14,13,12,8,10. — ankitgupta.1729, Jan 4, 2020
Yeah, I understood what you said but I am not able to digest it still.

you are directly swapping the values but the only way to do is heapify is what I know.

I still don't know what's wrong with the solution above which I have shown.

Can you please point out something there? — `JEET, Jan 5, 2020
Problem is to apply heapify, we should have heap structure. You have deleted the root node which have element 25. Now, in heapify procedure, we should have 3 elements to compare :node, its left and right children, which have max/min, we make it as parent but here when we delete 25 then there is no key value for this node then how we will compare and how max-heapify procedure will work. That's why I said after deleting 25, we should have to shift all remaining elements to left in the array and then apply max-heapify. — ankitgupta.1729, Jan 5, 2020
@abhishekmehta4u

Why is that when you are deleting 16, the value 8 comes up to be the root (in the 4th step). Why doesn't 14 come up ??

In that case, we will be having a different answer... — the_bob, Aug 23, 2018
@Satbir

Can you please explain this?

I am getting A as the answer — `JEET, Jan 4, 2020
After delete 16 it is wrong.

if a root is deleted then, the child which has higher value becomes the root. so 14 should become root. — Satbir, Jan 4, 2020

Akshay Koli 4 · Answer 1 · 2018-04-22T17:04:38+0000

Initial array 25, 14, 16 13, 10, 8. 12
after first deletion array became : 16 ,14 , 12 , 13 , 10 , 8 and
after second deletion array became 14 , 13, 12, 8 , 10

So option C is correct.

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

ISRO2018-57

Please log in or register to add a comment.

Please log in or register to answer this question.

2 Answers

Please log in or register to add a comment.

Please log in or register to add a comment.

Related questions

12 12 Comments reply

Please log in or register to add a comment.

Please log in or register to answer this question.

2 Answers

4 4 Comments reply

Please log in or register to add a comment.

0 reply

Please log in or register to add a comment.

Related questions

12 12 Comments

4 4 Comments

0