When a heap only has 1 node, is that node a leaf?

[Of Mike and Men]

Hey all,

So, I'm working on heaps, and looking at various implementations of heaps, I find that a lot of people us bool returning function for return (2*i+1 > n), where i is an index of a node stored in an array, and n is the size of the array. (2*i+1 is the formula to get the left child's position in the array). The function returns true if it is a leaf, false if it is not a leaf.

However, doesn't using 2*i+1 >= n make more sense? The case of 2*i+1 > n doesn't cover if i is your root node (IE 0), and n is only 1. Since 2(0)+1 = 1 > 1 returns false. Also by definition a node is a leaf if it has no children. I know this is kind of a special case, but it seems to be more consistent with definition of a leaf.

I guess I'm a little confused on what the proper definition would be symbolically.

 

[newjerseyrunner]

What language are you programming in? Some languages start at index 1, not zero. It's possible that your definition was for that kind of language.

Yes, in my opinion, a root with nothing beneath it is also a leaf.

 

[Of Mike and Men]

What language are you programming in? Some languages start at index 1, not zero. It's possible that your definition was for that kind of language.

Yes, in my opinion, a root with nothing beneath it is also a leaf.

C++ sorry, I should’ve included that in the OP. I see that assuming root with no children is a leaf, that it can cause issues with various algorithms (IE needing to check when there’s only 1 item in the heap as well as checking whether or not it’s a leaf in pop), so maybe it’s just for reducing the lines of code? But it seems irrelevant since it’d be constant time.

 

[QuantumQuest]

So, I'm working on heaps, and looking at various implementations of heaps, I find that a lot of people us bool returning function for return (2*i+1 > n), where i is an index of a node stored in an array, and n is the size of the array. (2*i+1 is the formula to get the left child's position in the array). The function returns true if it is a leaf, false if it is not a leaf.

The notion of a binary heap is based on the notion of a complete binary tree. You can assign the root an index #i = 1#. Then if some node has been assigned the index $i$, you assign its left child the index $2i$ and assign its right child $2i + 1$, if such child exists for each case. Then the tree is complete iff the set of assigned indices is a contiguous set. Now, in order to make the representation of a complete binary tree be contiguous starting at 0 you assign left child $2i + 1$ and the right child $2i + 2$.

Also by definition a node is a leaf if it has no children.

Yes, but if it is the only node and is also at the top of the heap i.e. has no parents, it is called the root node. From a theoretical standpoint, it does not make much sense to call it a leaf because in this way there is no parent node.