top of page

Show that, with the array representation for sorting an n-element heap, the leaves are the nodes indexed by floor(n/2+1), floor(n/2+2), โ€ฆ,n. What would be the location of the minimum element in the...

Let's take the left child of the node indexed by โŒŠ๐‘›/2โŒ‹+1โŒŠn/2โŒ‹+1.


LEFT(โŒŠ๐‘›/2โŒ‹+1)

=2(โŒŠ๐‘›/2โŒ‹+1)

>2(๐‘›/2โˆ’1)+2

=๐‘›โˆ’2+2

=n.โ€‹


Since the index of the left child is larger than the number of elements in the heap, the node doesn't have childrens and thus is a leaf. The same goes for all nodes with larger indices.

Note that if we take element indexed by โŒŠn/2โŒ‹, it will not be a leaf. In case of even number of nodes, it will have a left child with index n and in the case of odd number of nodes, it will have a left child with index nโˆ’1 and a right child with index n.


This makes the number of leaves in a heap of size n equal to โŒˆn/2โŒ‰.

23 views2 comments

2ไปถใฎใ‚ณใƒกใƒณใƒˆ


ใ‚ฒใ‚นใƒˆ
5ๆœˆ25ๆ—ฅ

I can't understand this statement: LEFT(โŒŠn/2โŒ‹+1)>2(n/2โˆ’1)+2

ใ„ใ„ใญ๏ผ
ใ‚ฒใ‚นใƒˆ
5ๆœˆ25ๆ—ฅ
่ฟ”ไฟกๅ…ˆ

ใ„ใ„ใญ๏ผ
bottom of page