1

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?

Kevin Meredith
  • 969

1 Answers1

0

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.

echinodermata
  • 4,219