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
logo

Crookshanks Academy is an online learning platform with free netflix styled courses.

Crookshanks Academy 2023 ©️ All Rights Reserved

This content is protected from right clicks.
bottom of page