An implementation in F# of the priority search queue described by R. Hinze in his paper 'A Simple Implementation Technique for Priority Search Queues'.
A priority search queue can serve as an associative map, mapping keys to values.
// Create queue that maps string keys to integer values (priorities)
let psq = [("C", 2); ("A", 3); ("B", 1)] |> PrioritySearchQueue.ofSeq
// Lookup entry with the key "A"
let key, value = psq |> PrioritySearchQueue.find "A"
// Add an entry with key "D" and value 1
let added = psq |> PrioritySearchQueue.add "D" 1
// Assign a value for entry with key "A" let updated = psq |> PrioritySearchQueue.add "A" 4
// Remove an entry with key "A"
let removed = psq |> PrioritySearchQueue.remove "A"
The search queue also functions as a priority queue, giving constant time access to the entry in the queue with the minimum value (priority).
// Retreive the entry with the minimum value. This will throw if the queue is empty.
let minKey, minValue = psq |> PrioritySearchQueue.min
// Use tryMin if the queue might be empty
let minVal = match psq |> PrioritySearchQueue.tryMin with
| Some( minKey, minValue) -> minValue
| None -> -1
// Remove the entry with the minimum value. This will throw if the queue is empty.
let minKey, minValue, rest = psq |> PrioritySearchQueue.removeMin
// Use tryRemoveMin if the queue might be empty
let minVal, rest = match psq |> PrioritySearchQueue.tryRemoveMin with
| Some(minKey, minValue, rest) -> minValue, rest
| None -> -1, PrioritySearchQueue.empty