Purely Functional Data Strutures presents the following question:
Chapter 3, Question 1:
"Prove that the right spine of a leftist heap of size n contains, at most, floor ( log ( n + 1) ) elements."
Earlier in the chapter, it explains:
"Leftish heaps are heap-ordered binary trees that satisfy the leftist property: the rank of any left child is at least as large as the rank of its right sibling."
Regarding the right spine, the book comments:
"The rank of a node is defined to be the length of its right spine, (i.e., the rightmost path from the node in question to an empty node)."
I drew, what I think, is a leftist heap where n == 4.
Please confirm that it's a valid leftist heap (for n = 4). If so, how can I calculate the right spine? Is it calculated per node - or a property in general for the whole heap?
The tree shown is leftist with a right spine of length 2. (I am using the word "tree" instead of "heap" since heap-ordering is irrelevant for the purpose of this question.) To put it another way, the rank of the node labeled 0 is 2.
The subtree whose root is the node labeled 2 is leftist with a right spine of length 1. That is, the rank of the node is 1.
Similarly for the others.