1.How does a leftist heap guarantee efficient merging?

an operation may be slow at times, but on average we have O(log n) merging.

since we merge right (following the shortest chain) we cant do more than log n operations

the answer is not mentioned

merging will never take less than log n time (so we have a tight bound)

we save in pointer space

2.How does one delete the largest value from a leftist min heap?

Replace the root with its inorder sucessor

We don't. Only delete min is allowed.

Replace the root with the smaller of its two children

3. Merge the two skew heaps below.

Which are the children of 11? List left child first.

32 33

33 32

32 16

wrong

The answer is not mentioned

16 32

4.Merge the (same) two skew heaps shown below.

Which are the children of 10? List left child first.

The answer is not mentioned

28 27

22 28

27 28

32 33

5.What is the principle behind skew heaps?

An operation may be slow at times, but on average we have O(log n) merging.

we save in pointer space

The answer is not mentioned

since we merge right (following the shortest chain) we cant do more than log n operations

merging will never take less than log n time (so we have a tight bound)

12 10 16 32 (41 27 28 50 12 10 16 32 (41 27 28 50