0501 (Friday, Week 4)

Edits after class look like this.

Q&A

Questions, comments, complaints?

Benefit of leftist property?

It ensures that the right spine is short, and thus that merging is fast.

Why leftist (and other) heap implementations rather than mutable array heaps?

Even when different implementations share the same worst-case complexity bounds, they may differ in other ways — such as the constant factors involved, average-case bounds, resilience to persistent use, difficulty to implement, etc.

The persistence of immutable data structures is also a nice property to have even in an imperative language. For example, Java strings are immutable, which is good for caching and efficiency, and ensures that they can safely be used as keys in a hash map
.

Does log2(n) mean log(log(n)) or log(n) * log(n) ?

log(n) * log(n)

Exercises

Weight-Biased Leftist Heaps

From the Okasaki textbook: "Weight-biased leftist heaps are an alternative to leftist heaps that replace the leftist property with the weight-biased leftist property: the size of any left child is at least as large as the size of its right sibling."

For a weight-biased leftist heap, let's use

  • w to refer to the size of its left child (w=0 if there is none) and
  • n to refer to its overall size.

Q: How many structurally distinct weight-biased leftist heaps for w=3 ?

Work through w=0, w=1, and w=2, keeping track of weights w and sizes n. Come up with some kind of pattern or shorthand, so that you don't have to draw all of the w=3 ones — there may be a lot!

Work with your breakout group, and we'll come back to discuss.

[answer below]

Before We Meet Again

  • (No lecture notes or videos before Monday's class)
  • Catch up on any homeworks and lectures
  • Work on project ideas
  • Prepare any topics for Q&A next time














Answers

For w=3, there are 10! (10, not 10!)