Safe Haskell	None
Language	GHC2021

Data.IntHeap.MaxTopK

Synopsis

data MaxTopK = MaxTopK !IntHeap !Int !Int !IntHeap
viewMaxTopK :: MaxTopK -> Int
viewMaxTopKList :: MaxTopK -> [Int]
newMaxTopK :: Int -> MaxTopK
buildMaxTopK :: Int -> [Int] -> MaxTopK
buildMaxTopKFromDescList :: Int -> [Int] -> MaxTopK
insertMaxTopK :: Int -> MaxTopK -> (Maybe Int, MaxTopK)
deleteMaxTopK :: Int -> MaxTopK -> (Maybe Int, MaxTopK)
exchangeMaxTopK :: Int -> Int -> MaxTopK -> (Maybe (Int, Int), MaxTopK)

Documentation

data MaxTopK Source #

Constructors

MaxTopK !IntHeap !Int !Int !IntHeap

Instances

Instances details

Show MaxTopK Source #
Instance details Defined in Data.IntHeap.MaxTopK Methods showsPrec :: Int -> MaxTopK -> ShowS # show :: MaxTopK -> String # showList :: [MaxTopK] -> ShowS #
Eq MaxTopK Source #
Instance details Defined in Data.IntHeap.MaxTopK Methods (==) :: MaxTopK -> MaxTopK -> Bool # (/=) :: MaxTopK -> MaxTopK -> Bool #

viewMaxTopK :: MaxTopK -> Int Source #

O(1)

>>> viewMaxTopK (buildMaxTopK 3 [0..9])
7

viewMaxTopKList :: MaxTopK -> [Int] Source #

O(k)

>>> viewMaxTopKList (buildMaxTopK 3 [0..9])
[9,8,7]

newMaxTopK :: Int -> MaxTopK Source #

buildMaxTopK :: Int -> [Int] -> MaxTopK Source #

O(n log n)

>>> buildMaxTopK 4 [0..4]
([4,3,2,1],[0])
>>> buildMaxTopK 4 [0..3]
([3,2,1,0],[-9223372036854775808])
>>> buildMaxTopK 4 [0..2]
([2,1,0,-9223372036854775808],[-9223372036854775808])

buildMaxTopKFromDescList :: Int -> [Int] -> MaxTopK Source #

O(n)

>>> buildMaxTopKFromDescList 3 [2,2,1,1,0,0]
([2,2,1],[1,0,0])

insertMaxTopK Source #

Arguments

:: Int
-> MaxTopK
-> (Maybe Int, MaxTopK)	Maybe deleted

O(min(n,W))

>>> maxTop4 = buildMaxTopK 4 [0..4]
>>> maxTop4
([4,3,2,1],[0])
>>> insertMaxTopK 999 maxTop4
(Just 1,([999,4,3,2],[1,0]))
>>> insertMaxTopK (-999) maxTop4
(Nothing,([4,3,2,1],[0,-999]))
>>> insertMaxTopK 1 maxTop4
(Nothing,([4,3,2,1],[1,0]))

deleteMaxTopK Source #

Arguments

:: Int
-> MaxTopK
-> (Maybe Int, MaxTopK)	Maybe inserted

O(min(n,W))

>>> maxTop3 = buildMaxTopK 3 [0,1,1,2,2]
>>> maxTop3
([2,2,1],[1,0])
>>> deleteMaxTopK 2 maxTop3
(Just 1,([2,1,1],[0]))
>>> deleteMaxTopK 1 maxTop3
(Nothing,([2,2,1],[0]))
>>> deleteMaxTopK 0 maxTop3
(Nothing,([2,2,1],[1]))
>>> deleteMaxTopK 999 maxTop3
(Nothing,([2,2,1],[1,0]))
>>> deleteMaxTopK (-999) maxTop3
(Nothing,([2,2,1],[1,0]))
>>> deleteMaxTopK 2 $ buildMaxTopK 3 [2,2,2,2,2]
(Nothing,([2,2,2],[2]))
>>> deleteMaxTopK 0 $ buildMaxTopK 1 [0]
(Just (-9223372036854775808),([-9223372036854775808],[-9223372036854775808]))

exchangeMaxTopK Source #

Arguments

:: Int	old
-> Int	new
-> MaxTopK
-> (Maybe (Int, Int), MaxTopK)	Maybe (inserted, deleted)

O(min(n,W))

>>> maxTop3 = buildMaxTopK 3 [0,1,1,2,2]
>>> maxTop3
([2,2,1],[1,0])
>>> exchangeMaxTopK 2 999 maxTop3
(Just (999,2),([999,2,1],[1,0]))
>>> exchangeMaxTopK 1 999 maxTop3
(Just (999,1),([999,2,2],[1,0]))
>>> exchangeMaxTopK 0 999 maxTop3
(Just (999,1),([999,2,2],[1,1]))
>>> exchangeMaxTopK 2 1 maxTop3
(Just (1,2),([2,1,1],[1,0]))
>>> exchangeMaxTopK 0 1 maxTop3
(Nothing,([2,2,1],[1,1]))
>>> exchangeMaxTopK 1 1 maxTop3
(Nothing,([2,2,1],[1,0]))
>>> exchangeMaxTopK 999 999999 maxTop3
(Nothing,([2,2,1],[1,0]))
>>> exchangeMaxTopK 0 999 $ buildMaxTopK 1 [0, 0]
(Just (999,0),([999],[0]))