CODEWITHSUNDEEP
algorithm
user1766888
user1766888

Reputation: 409

Array representation of a min-heap

If an array is has a size of 20 (0-19) and the mapping is from (i-1)/2 to a parent. What does mapping of (i-1)/2 mean in relation to representing a min-heap of a size of 13?

Upvotes: 0

Views: 6086

Answers (1)

rrufai
rrufai

Reputation: 1495

As Dan said the mapping is the same whatever the size of the array. If it helps, here is the binary heap tree for the example you provided, with the second 70 (in level 3) changed to 71. Binary heap tree

You can get the binary heap array by traversing the tree top-down, left-to-right. Below is the resulting array with the indices shown below, so you can easily apply the mapping to an index and see what value occurs there and cross check with the tree rendition.

array  :  10 | 20 | 25 | 60 |  30 | 58 | 71 | 99 | 70 |  82 | 50 | 90 | 85
indices:   0 |  1 |  2 |  3 |   4 |  5 |  6 |  7 |  8 |   9 | 10 | 11 | 12

I hope this clears up your doubts.

Upvotes: 2

Related Questions