Purely functional Priority Queue · Memetic Musings

Purely functional Priority Queue · Memetic Musings

Life long learner. Eclectic. Likes to read, code, play badminton. This is part of a series of articles on implementing various functional data structures in Scala. See other articles in this series: In this part we will implement a basic Priority Queue in Scala. It will support the following operations efficiently: abstract class PriorityQueue[A](implicit val ord: Ordering[A]) { // Add an item def +(x: A) : PriorityQueue[A] // Find min item def findMin: A // New Priority queue with min item deleted def deleteMin(): PriorityQueue[A] // Merges two PriorityQueue together def meld(that: PriorityQueue[A]) : PriorityQueue[A] } Basics There are different ways to implement a Priority Queue. We will use Binomial Heap . As usual we follow the approach from Okasaki. See this paper for details about implementing efficient and purely functional priority queues. We start with the basic implementation which is simple to understand. If you know how Binomial heaps work, skip to the next section.

Read full article from Purely functional Priority Queue · Memetic Musings