MyQuestionIcon

1

You visited us 1 times! Enjoying our articles? Unlock Full Access!

Heap Sort II

Consider an a...

Question

Consider an array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored in index i of the array (i < =n), the index of the parent is

A

ceiling (i/2)

No worries! We‘ve got your back. Try BYJU‘S free classes today!

B

floor ((i - 2)/2)

No worries! We‘ve got your back. Try BYJU‘S free classes today!

C

floor (i/2)

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

D

ceiling ((i + 2)/2)

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

The correct option is C floor (i/2)
If array index is starting from '1' then for any node whose index 'i' its left child at index 2i and right child at index 2i + 1 and its parent index at $⌊ \frac{i}{2} ⌋$

Suggest Corrections

thumbs-up

0

Similar questions

Q. In a compact single dimensional array representation for lower triangular matrices (i.e. all the elements above the diagonal are zero) of size n

\times

n, non-zero elements (i.e. elements of the lower triangle) of each row are stored one after another, starting from the first row, the index of the

(i, j)^{t h}

element of the lower triangular matrix in this new representation is

Q. An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0.

If the root node is at level 0, the level of element X[i], i

\neq

Q. An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0.

If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of

Q. A binary min heap consisting of integers is implemented using array A[1 ....n] in which root node is stored at A[1] and locations A[1] through A[n] store the 'n' integer values in the heap. The minimum number of comparisons required to find maximum element in a min heap of 99 elements is

Q. Consider the following two C code segments. Y and X are one and two dimensional arrays of size n and

n \times n

respectively, where

2 \leq n \geq 10.

Assume that in both code segments, elements of Y are initialized to 0 and each element X[i][j] of array X is initialized to i + j. Further assume that when stored in main memory all elements of X are in same main memory page frame.

Code segment 1 :
// initialize elements of Y to 0
// initialize elements X [i][j] of X to i+j
for (i =0; i < n; i++)
Y [i] + = X [0] [i];

Code segment 2 :
// initialize elements of Y to 0
// initialize elements X[i][j] of X to i+j
for (i =0; i < n; i++)
Y [i] + = X [i] [0];

Which of the following statements is/are correct?

S1 : Final contents of array Y will be same in both code segments.

S2 : Elements of array X accessed inside the for loop shown in code segment 1 are contiguous in main memory.

S3 : Elements of array X accessed inside the for loop shown in code segment 2 are contiguous in main memory.

View More

Join BYJU'S Learning Program

explore_more_icon

Explore more

Join BYJU'S Learning Program

CrossIcon