Safe Haskell | Safe |
---|
PriorityQueue
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
- data PriorityQueue p v
- empty :: PriorityQueue p v
- singleton :: Ord p => p -> v -> PriorityQueue p v
- fromList :: Ord p => [(p, v)] -> PriorityQueue p v
- insert :: Ord p => p -> v -> PriorityQueue p v -> PriorityQueue p v
- union :: Ord p => PriorityQueue p v -> PriorityQueue p v -> PriorityQueue p v
- isEmpty :: PriorityQueue p v -> Bool
- size :: PriorityQueue p v -> Int
- getTop :: Ord p => PriorityQueue p v -> Maybe (p, v)
- toDescList :: Ord p => PriorityQueue p v -> [(p, v)]
- extractTop :: Ord p => PriorityQueue p v -> PriorityQueue p v
- extractGetTop :: Ord p => PriorityQueue p v -> Maybe ((p, v), PriorityQueue p v)
- replaceTop :: Ord p => p -> v -> PriorityQueue p v -> PriorityQueue p v
- modifyTop :: Ord p => (p -> v -> Maybe (p, v)) -> PriorityQueue p v -> PriorityQueue p v
- valid :: Show p => Ord p => PriorityQueue p v -> Bool
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 |
(Show p, Show v, Ord p) => Show (PriorityQueue p v) | O(n log n). Define instance of
|
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 PriorityQueue
s.
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.