Great stuff.
As an aside, in "Playing with Priority Queues", Louis provides a number of heaps but stops short of one with O(1) worst-case persistent insert.I have an implementation of Brodal/Okasaki heaps that achieves those bounds that is available on hackage.
http://hackage.haskell.org/package/heaps
As he notes, it does make the implementation harder to follow, but it may be of interest for the reader who wants to dig into this space further. =)
If I have enough downtime, I'm hoping to add a functional version of Chazelle-style soft heaps to the library as well, which gives O(log(1/epsilon)) delete at the expense of corrupting (increasing) an epsilon worth of the keys in your heap, which is actually quite useful for a number of deterministic algorithms, like an O(n) median finding algorithm, and the fast construction of minimum spanning trees.
-Edward Kmett