Inspired by an email where Slava proposed that Factor begin to use more persistent data structures, I implemented a functional priority queue (minheap). It's in the main Factor repository in extra/persistent-heaps. Strangely, the Haskell Hierarchical Libraries don't seem to have a priority queue implementation, but there's a nice literate program by Michael Richter implementing them in Haskell, and my implementation is generally similar to that. (Neither one really takes advantage of laziness.)
They're based on a really cool idea that's described in the book ML for the Working Programmer by L. C. Paulson. Instead of pushing onto a heap by putting an element at the end of the array and percolating up, we can add it going down from the top. This frees us from the use of the array, allowing a functional pointer-based structure to be used. The heap can be balanced if we alternate back and forth which side we push onto. This can be done easily if we always push on to the right side and then swap the left and the right sides (unless the priority is the least, in which case we relegate the old top value to go to the right side and swap the sides).
