Safe HaskellSafe

PriorityQueue

Contents

Description

Second assignment for IB016 Seminar on Functional Programming, spring 2016

Your task is to implement a priority queue based on heap data structure. A priority queue is a data structure which holds values sorted by priority (so that the value with the highest priority is at the top of the heap). The interface is given by this file, together with suggested time complexities for each of the functions. Your implementation should meet these time complexities.

It is suggested to use binary heap. You can also use more advanced versions of heaps, for example binomial heap or Fibonacci heap. It is possible to meet all the requirements with binary heap which is reasonably simple to implement. You can get extra points for more advanced heap implementations.

You may define your own (internal) functions that the module does not export (e.g. helper functions for tree rotations and such). You are not required (but still strongly encouraged) to document such functions using the Haddock markup. You can use any modules from the Base package if you wish. However, you may not use any other packages.

Name: Name Surname UID: 123456

Synopsis

Priority Queue Type

data PriorityQueue p v

Defines a PriorityQueue type. It should implement a (binary) heap. Note that the data constructors of this type are not exported from the module to disallow direct manipulations. (If they should have been exported the module header entry would read PriorityQueue (..)).

Note: You should define Show and Functor instances. Show should be defined by hand, not derived. Nevertheless, it is useful to derive Show instance during development and change to a custom-defined instance once you trust your implementation.

Instances

Functor (PriorityQueue p)

Define PriorityQueue p to be an instance of Functor, keep in mind the standard behaviour of Functor.

(Show p, Show v, Ord p) => Show (PriorityQueue p v)

O(n log n). Define instance of Show similar to the one for Map.

>>> show empty
"fromList []"
>>> show $ singleton 42 ()
"fromList [(42,())]

Construction

empty :: PriorityQueue p v

O(1). An empty PriorityQueue.

>>> empty
fromList []

singleton :: Ord p => p -> v -> PriorityQueue p v

O(1). A PriorityQueue with a single element.

>>> singleton 42 "hi"
fromList [(42,"hi")]

fromList :: Ord p => [(p, v)] -> PriorityQueue p v

O(n log n). Build a PriorityQueue from a list of priority – value pairs.

Note: this can be done in O(n), you can be awarded bonus points if you implement this version.

>>> fromList [(0, ()), (4, ()), (17, ()), (3, ())]
fromList [(17,()),(4,()),(3,()),(0,())]

insert :: Ord p => p -> v -> PriorityQueue p v -> PriorityQueue p v

O(log n). insert prio val pq inserts the element val with the priority prio into the PriorityQueue pq.

>>> insert 42 "hi" empty
fromList [(42,"hi")]
>>> insert 0 "" $ singleton 42 "hi"
fromList [(42,"hi"),(0,"")]

union :: Ord p => PriorityQueue p v -> PriorityQueue p v -> PriorityQueue p v

O(n log n). Compute union of two PriorityQueues.

Note: this can be done in O(n), you can be awarded bonus points if you implement this version.

>>> fromList [(0, ()), (4, ()), (17, ()), (3, ())] `union` singleton 42 ()
fromList [(42,()),(17,()),(4,()),(3,()),(0,())]

Querying

isEmpty :: PriorityQueue p v -> Bool

O(1). Is the PriorityQueue empty?

>>> isEmpty empty
True
>>> isEmpty $ singleton 42 "hi"
False

size :: PriorityQueue p v -> Int

O(1). The number of elements in the PriorityQueue.

>>> size $ singleton 42 "hi"
1

getTop :: Ord p => PriorityQueue p v -> Maybe (p, v)

O(1). Get the element with highest priority from the given PriorityQueue. Returns Nothing if and only if the PriorityQueue is empty.

>>> getTop $ insert 0 "" $ singleton 42 "hi"
Just (42,"hi")
>>> getTop empty
Nothing

toDescList :: Ord p => PriorityQueue p v -> [(p, v)]

O(n log n). Convert the given PriorityQueue to a list of its priority – value pairs ordered by priority in descending order.

>>> toDescList $ fromList [(0, ()), (4, ()), (17, ()), (3, ())]
[(17,()),(4,()),(3,()),(0,())]

Modification

extractTop :: Ord p => PriorityQueue p v -> PriorityQueue p v

O(log n). Extract (remove) the element with highest priority from the given PriorityQueue. Returns empty if the PriorityQueue is empty.

>>> extractTop $ insert 0 "" $ singleton 42 "hi"
fromList [(0,"")]
>>> extractTop empty
fromList []

extractGetTop :: Ord p => PriorityQueue p v -> Maybe ((p, v), PriorityQueue p v)

O(log n). Get and extract the element with highest priority from the given PriorityQueue. Returns Nothing if and only if the PriorityQueue is empty.

>>> extractGetTop $ insert 0 "" $ singleton 42 "hi"
Just ((42,"hi"),fromList [(0,"")])
>>> extractGetTop empty
Nothing

replaceTop :: Ord p => p -> v -> PriorityQueue p v -> PriorityQueue p v

O(log n). Replace the highest priority element with new priority and value.

>>> replaceTop 2 "a" $ fromList [(1, ""), (3, "")]
fromList [(2,"a"),(1,"")]
>>> replaceTop 0 "a" $ fromList [(1, ""), (3, "")]
fromList [(1,""),(0,"a")]

modifyTop :: Ord p => (p -> v -> Maybe (p, v)) -> PriorityQueue p v -> PriorityQueue p v

O(log n). Replace the highest priority element using a function callback which is called with the current priority and value of the top element. If the callback returns Nothing the root is removed, otherwise new values of priority and value are determined from the returned Just value.

>>> modifyTop (\k v -> Just (k + 2, v)) $ fromList [(1, ""), (2, "")]
fromList [(4,""),(1,"")]
>>> modifyTop (\k v -> Just (k - 2, v)) $ fromList [(1, ""), (2, "")]
fromList [(1,""),(0,"")]

Debugging

valid :: Show p => Ord p => PriorityQueue p v -> Bool

Check validity of a given PriorityQueue, this should validate that size returns the right value for the heap and all its subheaps and that all the requirements given by the data structure are met (e.g. for binary heap, it should check that the tree is left aligned, lengths of paths from root to leaf differ at most by one, and that the priority is nonascending on every path from root to leaf). You should use this function for testing.