Priority queue: Difference between revisions
→{{header|Haskell}}: Add "mergePQ" function and clean up code...
GordonBGood (talk | contribs) (→{{header|C sharp}}: fix adj/popMin methods and test adjust...) |
GordonBGood (talk | contribs) (→{{header|Haskell}}: Add "mergePQ" function and clean up code...) |
||
Line 1,617:
The above code is a Priority Queue but isn't a [https://en.wikipedia.org/wiki/Binary_heap Min Heap based on a Binary Heap] for the following reasons: 1) it does not preserve the standard tree structure of the binary heap and 2) the tree balancing can be completely destroyed by some combinations of "pop" operations. The following code is a true purely functional Min Heap implementation and as well implements the extra optional features of Min Heap's that it can build a new Min Heap from a list in O(n) amortized time rather than the O(n log n) amortized time (for a large number of randomly ordered entries) by simply using repeated "push" operations; as well as the standard "push", "peek", "delete" and "pop" (combines the previous two). As well as the "fromList", "toList", and "sort" functions (the last combines the first two), it also has an "isEmpty" function to test for the empty queue, an "adjust" function that applies a function to every entry in the queue and reheapifies in O(n) amortized time and also the "replaceMin" function which is about twice as fast on the average as combined "delete" followed by "push" operations:
<lang haskell>data MinHeap kv = MinHeapEmpty
| MinHeapLeaf !kv
| MinHeapNode !kv {-# UNPACK #-} !Int !(MinHeap a) !(MinHeap a)
Line 1,741 ⟶ 1,740:
sortPQ :: (Ord kv) => [kv] -> [kv]
sortPQ ls = toListPQ $ fromListPQ ls</lang>
If one is willing to forgo the fast O(1) "size" function and to give up strict conformance to the Heap tree structure (where rather than building each new level until each left node is full to that level before increasing level to the right, a new level is built by promoting leaves to branches only containing left leaves until all branches have left leaves before filling any right leaves of that level) although having even better tree balancing and therefore at least as high efficiency, one can use the following code adapted from the [http://www.cl.cam.ac.uk/~lp15/MLbook/programs/sample4.sml ''ML'' PRIORITY_QUEUE code by Lawrence C. Paulson] including separating the key/value pairs as separate entries in the data structure for better comparison efficiency; as noted in the code comments, a "size" function to output the number of elements in the queue (fairly quickly in O((log n)^2)), an "adjust" function to apply a function to all elements and reheapify in O(n) time, and a "merge" function to merge two queues has been added to the ML code:
<lang haskell>data PriorityQ k v = Mt
| Br !k v !(PriorityQ k v) !(PriorityQ k v)
deriving (Eq, Ord, Read, Show)
Line 1,752 ⟶ 1,749:
emptyPQ :: PriorityQ k v
emptyPQ = Mt
isEmptyPQ :: PriorityQ k v -> Bool
isEmptyPQ Mt = True
Line 1,764 ⟶ 1,761:
sizePQ :: PriorityQ k v -> Int
sizePQ Mt = 0
sizePQ (Br _ _
n = sizePQ
-- rest n p q, where n = sizePQ q, and sizePQ p - sizePQ q = 0 or 1
-- returns 1 + sizePQ p - sizePQ q.
Line 1,771 ⟶ 1,768:
rest 0 Mt _ = 1
rest 0 _ _ = 2
rest n (Br _ _
0 -> rest d
1 -> rest d
where
d = m1 `shiftR` 1
r = m1 .&. 1
peekMinPQ :: PriorityQ k v -> Maybe (k, v)
Line 1,782 ⟶ 1,781:
pushPQ :: Ord k => k -> v -> PriorityQ k v -> PriorityQ k v
pushPQ wk wv Mt = Br wk wv Mt Mt
pushPQ wk wv (Br vk vv
| wk <= vk = Br wk wv (pushPQ vk vv
| otherwise = Br vk vv (pushPQ wk wv
siftdown :: Ord k => k -> v -> PriorityQ k v -> PriorityQ k v -> PriorityQ k v
Line 1,810 ⟶ 1,809:
(k, v, Br vk vv pr npl)
-- the following function has been added to the ML code to apply a function
-- to all the entries in the queue and reheapify in O(n) time
adjustPQ :: (Ord k) => (k -> v -> (k, v)) -> PriorityQ k v -> PriorityQ k v
adjustPQ f pq = adjust pq where -- applies function to every element and reheapifies
Line 1,824 ⟶ 1,825:
(pr, xrr) = build ((lvl - 1) `shiftR` 1) xrl in
(siftdown k v pl pr, xrr)
-- the following function has been added to merge two queues in O(m + n) time
-- where m and n are the sizes of the two queues
mergePQ :: (Ord k) => PriorityQ k v -> PriorityQ k v -> PriorityQ k v
mergePQ pq1 Mt = pq1 -- from concatenated "dumb" list
mergePQ Mt pq2 = pq2 -- in O(m + n) time where m,n are sizes pq1,pq2
mergePQ pq1 pq2 = fromListPQ (zipper pq1 $ zipper pq2 []) where
zipper (Br wk wv Mt _) appndlst = (wk, wv) : appndlst
zipper (Br wk wv pl Mt) appndlst = (wk, wv) : zipper pl appndlst
zipper (Br wk wv pl pr) appndlst = (wk, wv) : zipper pl (zipper pr appndlst)
popMinPQ :: (Ord k) => PriorityQ k v -> Maybe ((k, v), PriorityQ k v)
Line 1,835 ⟶ 1,846:
sortPQ :: (Ord k) => [(k, v)] -> [(k, v)]
sortPQ ls = toListPQ $ fromListPQ ls</lang>
The above codes compile but do not run with GHC Haskell version 7.8.3 using the LLVM back end with LLVM version 3.4 and full optimization turned on under Windows 32; they were tested under Windows 64 and 32 using the Native Code Generator back end with full optimization. With GHC Haskell version 7.10.1 they compile and run with or without LLVM 3.5.1 for 32-bit Windows (64-bit GHC Haskell under Windows does not run with LLVM for version 7.10.1), with a slight execution speed advantage to using LLVM.
Min Heaps are faster than Priority Queue's based on Binomial Heaps (or Leftist or Skewed Heaps) when one mainly requires fast replacement of the head of the queue
Min Heaps are also faster than the use of balanced tree Set's or Map's where many references are made to the next element in the queue (O(1) complexity rather than O(log n)) or where frequent modification and reinsertion of the next element in the queue is required (still O(log n) but faster by a constant factor greater than two on average) and generally faster by a constant factor as operations near the top of the queue don't have to traverse the entire tree structure; O(log n) is worst case time complexity for "replace" operations not average.
The above codes when tested with the following "main" function (with a slight modification for the first test when the combined kv entry is used):
<lang haskell>testList = [ (3, "Clear drains"),
(4, "Feed cat"),▼
main = mapM_ print $ toListPQ $ foldl (flip pushPQ) emptyPQ [▼
(
(
(
(1, "Solve RC tasks"),▼
(2, "Tax return")]▼
testPQ = fromListPQ testList
main = mapM_ print $ toListPQ $ fromListPQ [▼
(3, "Clear drains"),▼
▲ (4, "Feed cat"),
(5, "Make tea"),▼
(1, "Solve RC tasks"),▼
(2, "Tax return")]▼
main = do -- slow build
putStrLn "" -- fast build
main = mapM_ print $ sortPQ [▼
(3, "Clear drains"),▼
putStrLn "" -- combined fast sort
(4, "Feed cat"),▼
(5, "Make tea"),▼
putStrLn "" -- test merge
(1, "Solve RC tasks"),▼
mapM_ print $ toListPQ $ mergePQ testPQ testPQ
(2, "Tax return")]▼
putStrLn "" -- test adjust
mapM_ print $ toListPQ $ adjustPQ (\x y -> (x * (-1), y)) testPQ</lang>
{{output}}
(1,"Solve RC tasks")
(2,"Tax return")
Line 1,882 ⟶ 1,887:
(4,"Feed cat")
(5,"Make tea")
(4,"Feed cat")
(1,"Solve RC tasks")
(2,"Tax return")
(3,"Clear drains")
(3,"Clear drains")
(4,"Feed cat")
(4,"Feed cat")
(5,"Make tea")
(5,"Make tea")
(-5,"Make tea")
(-4,"Feed cat")
(-3,"Clear drains")
(-2,"Tax return")
(-1,"Solve RC tasks")</pre>
but the first method uses the slower way of building a queue.
=={{header|Icon}} and {{header|Unicon}}==
| |||