Question 12

To sort a sequence of integers 1 through 8 in descending order using the heap sort method, the whole sequence is turted into a heap as follows:

1,4,2,5,8,3,6,7

Here, the first and last element are exchanged as follows:

7,4,2,5,8,3,6,1

Then, a procedure is executed to turn the underlined part into a heap. Which of the following represents the sequence just after the execution of the sort? Here, the heap is implemented as a complete binary tree in which the first (leftmost) element of the sequence is the root and the children of the ith element of the sequence are the 2ith and (2i + 1)th elements.

a) 2,4,3,5,8,7,6,1
b) 4,2,5,8,3,6,7,1
c) 7,4,5,8,3,6,2,1
d) 8,7,6,5,4,3,2,1

answer

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: