Yesterday, I finished the draft of the Heaps chapter of Functional Data Structures in R. It got a little shorter than I had planned, but instead the chapter on Immutable and persistent data got a little longer.
I had planned to include Brodal heaps in this chapter, but ended up not doing it. They are pretty cool in having optimal worst-case complexity, but there isn’t much novel in how you would implement them in R compared to binomial heaps. Instead, I described how skew-binomial numbers can be used as a framework for random access lists. That is one of the ideas that are used in Brodal heaps, but by using it for lists I get to show the trick without repeating too much code compared to what I would need to do for Brodal heaps.
Now I just have one more chapter to write before I start editing. The chapter on Sets, maps and search trees. There, I will include red-black trees—these can be handled very elegantly if you never delete elements, but it is possible to delete elements with some work that I still have to implement—and I will include splay trees. I don’t know exactly what to include beyond that.
Anyway, the current plan is that this will be the last chapter, but if I can think about something more to add, I might. If not, I will finish the draft and then let the book rest a few weeks so I can edit it with fresh eyes. While this book is resting, I will find something else to write on.