Priority queue is a collection that gives an easy access to its smallest (or largest) item.
Priority queues are good at accessing the smallest/largest item (O(1) for head, smallest and largest), while they're slower at inserting and deleting items (O(log n) for insert and dequeue).
Contrast this to linked lists (Elm's List) which are fast at inserting and deleting items (O(1) for cons and tail) but slow at finding the smallest/largest item (O(n) for minimum and maximum).
This package is a fork of fifth-postulate/priority-queue that:
- makes it easier (by naming the types explicitly) to know which "direction" the queue goes (items with smaller priority Ints first, or the other way round)
- contains a more complete API (eg.
singleton,filter,length,any, etc.) - doesn't hold a function inside the data structure (thus is usable in the Elm debugger etc.)
import MaxPriorityQueue exposing (MaxPriorityQueue)
type alias BuyOffer =
{ amount : Int
, unitPrice : Int
}
offersByPrice : MaxPriorityQueue BuyOffer
offersByPrice =
MaxPriorityQueue.fromList .unitPrice
[ { amount = 10, unitPrice = 3000 }
, { amount = 15, unitPrice = 10000 }
, { amount = 100, unitPrice = 2000 }
]
bestOffer =
MaxPriorityQueue.largest offersByPrice
--> Just { amount = 1, unitPrice = 10000 }
bestAndRest =
MaxPriorityQueue.dequeue offersByPrice
--> Just
-- ( { amount = 15, unitPrice = 10000 }
-- , MaxPriorityQueue.fromList .unitPrice
-- [ { amount = 10, unitPrice = 3000 }
-- , { amount = 100, unitPrice = 2000 }
-- ]
-- )
nextBest =
bestAndRest
|> Maybe.andThen (\(_, rest) -> MaxPriorityQueue.largest rest)
--> Just { amount = 10, unitPrice = 3000 }MinPriorityQueue works similarly, just has smallest instead of largest in its functions:
import MinPriorityQueue exposing (MinPriorityQueue)
type alias Person =
{ name : String
, age : Int
}
peopleByAge : MinPriorityQueue Person
peopleByAge =
MinPriorityQueue.fromList .age
[ Person "Martin" 31
, Person "Xavier" 13
, Person "Joanne" 54
]
youngest : Maybe Person
youngest =
MinPriorityQueue.smallest peopleByAge
--> Just { name = "Xavier", age = 13 }MinPriorityQueue and MaxPriorityQueue are implemented using leftist heaps (see Purely Functional Data Structures by Okasaki, chapter 3.1).
