In the opposite direction of pragmatically avoiding "fancy" data-structures, you can find a description of a persistent min-heap via Brodal queues in Chris Okasaki's wonderful book _Purely Functional Data Structures_. Otherwise, it doesn't make too much sense to use the Fibonacci heap algorithm without mutable update.