Safe Haskell	Safe-Inferred
Language	GHC2021

Data.IntHeap

Synopsis

newtype IntHeap = IntHeap {
- getIntHeap :: IntMap Int
}
emptyIH :: IntHeap
singletonIH :: Int -> IntHeap
replicateIH :: Int -> Int -> IntHeap
fromListIH :: [Int] -> IntHeap
fromAscListIH :: [Int] -> IntHeap
fromDistinctAscListIH :: [Int] -> IntHeap
fromDescListIH :: [Int] -> IntHeap
fromDistinctDescListIH :: [Int] -> IntHeap
toListIH :: IntHeap -> [Int]
toAscListIH :: IntHeap -> [Int]
toDescListIH :: IntHeap -> [Int]
insertIH :: Int -> IntHeap -> IntHeap
deleteIH :: Int -> IntHeap -> IntHeap
deleteAllIH :: Int -> IntHeap -> IntHeap
memberIH :: Int -> IntHeap -> Bool
notMemberIH :: Int -> IntHeap -> Bool
countIH :: Int -> IntHeap -> Int
lookupLTIH :: Int -> IntHeap -> Maybe Int
lookupGTIH :: Int -> IntHeap -> Maybe Int
lookupLEIH :: Int -> IntHeap -> Maybe Int
lookupGEIH :: Int -> IntHeap -> Maybe Int
nullIH :: IntHeap -> Bool
sizeIH :: IntHeap -> Int
findMinIH :: IntHeap -> Int
findMaxIH :: IntHeap -> Int
deleteMinIH :: IntHeap -> IntHeap
deleteMaxIH :: IntHeap -> IntHeap
deleteFindMinIH :: IntHeap -> (Int, IntHeap)
deleteFindMaxIH :: IntHeap -> (Int, IntHeap)
minViewIH :: IntHeap -> Maybe (Int, IntHeap)
maxViewIH :: IntHeap -> Maybe (Int, IntHeap)
splitIH :: Int -> IntHeap -> (IntHeap, IntHeap)
splitLookupIH :: Int -> IntHeap -> (IntHeap, [Int], IntHeap)

Documentation

newtype IntHeap Source #

Constructors

IntHeap
Fields getIntHeap :: IntMap Int

Instances

Instances details

IsList IntHeap Source #
Instance details Defined in Data.IntHeap Associated Types type Item IntHeap # Methods fromList :: [Item IntHeap] -> IntHeap # fromListN :: Int -> [Item IntHeap] -> IntHeap # toList :: IntHeap -> [Item IntHeap] #
Show IntHeap Source #
Instance details Defined in Data.IntHeap Methods showsPrec :: Int -> IntHeap -> ShowS # show :: IntHeap -> String # showList :: [IntHeap] -> ShowS #
Eq IntHeap Source #
Instance details Defined in Data.IntHeap Methods (==) :: IntHeap -> IntHeap -> Bool # (/=) :: IntHeap -> IntHeap -> Bool #
type Item IntHeap Source #
Instance details Defined in Data.IntHeap type Item IntHeap = Int

emptyIH :: IntHeap Source #

singletonIH :: Int -> IntHeap Source #

replicateIH :: Int -> Int -> IntHeap Source #

O(1)

>>> replicateIH 3 1
[1,1,1]
>>> nullIH $ replicateIH 0 1
True
>>> nullIH $ replicateIH (-1) 1
True

fromListIH :: [Int] -> IntHeap Source #

O(n min(n,W))

>>> fromListIH [0,1,2,1,0]
[0,0,1,1,2]

fromAscListIH :: [Int] -> IntHeap Source #

O(n)

>>> fromAscListIH [0,0,1,2]
[0,0,1,2]

fromDistinctAscListIH :: [Int] -> IntHeap Source #

O(n)

>>> fromDistinctAscListIH [0,1,2]
[0,1,2]

fromDescListIH :: [Int] -> IntHeap Source #

O(n)

>>> fromDescListIH [2,1,0,0]
[0,0,1,2]

fromDistinctDescListIH :: [Int] -> IntHeap Source #

O(n)

>>> fromDistinctDescListIH [2,1,0]
[0,1,2]

toListIH :: IntHeap -> [Int] Source #

O(n)

>>> toListIH (fromListIH [0,1,0,2])
[0,0,1,2]

toAscListIH :: IntHeap -> [Int] Source #

O(n)

>>> toAscListIH (fromListIH [0,1,0,2])
[0,0,1,2]

toDescListIH :: IntHeap -> [Int] Source #

O(n)

>>> toDescListIH (fromListIH [0,1,0,2])
[2,1,0,0]

insertIH :: Int -> IntHeap -> IntHeap Source #

O(min(n,W))

deleteIH :: Int -> IntHeap -> IntHeap Source #

O(min(n,W))

>>> deleteIH 0 (fromList [0, 0, 1, 2])
[0,1,2]
>>> deleteIH 3 (fromList [0, 0, 1, 2])
[0,0,1,2]

deleteAllIH :: Int -> IntHeap -> IntHeap Source #

O(min(n,W))

>>> deleteAllIH 0 (fromList [0, 0, 1, 2])
[1,2]
>>> deleteAllIH 3 (fromList [0, 0, 1, 2])
[0,0,1,2]

memberIH :: Int -> IntHeap -> Bool Source #

O(min(n,W))

notMemberIH :: Int -> IntHeap -> Bool Source #

O(min(n,W))

countIH :: Int -> IntHeap -> Int Source #

O(min(n, W))

>>> countIH 0 (fromList [0, 0, 1, 2])
2
>>> countIH 1 (fromList [0, 0, 1, 2])
1
>>> countIH (-1) (fromList [0, 0, 1, 2])
0

lookupLTIH :: Int -> IntHeap -> Maybe Int Source #

O(log n)

>>> lookupLTIH 1 (fromList [0, 0, 1, 1, 2, 2])
Just 0
>>> lookupLTIH 0 (fromList [0, 0, 1, 1, 2, 2])
Nothing

lookupGTIH :: Int -> IntHeap -> Maybe Int Source #

O(log n)

>>> lookupGTIH 1 (fromList [0, 0, 1, 1, 2, 2])
Just 2
>>> lookupGTIH 2 (fromList [0, 0, 1, 1, 2, 2])
Nothing

lookupLEIH :: Int -> IntHeap -> Maybe Int Source #

O(log n)

>>> lookupLEIH 1 (fromList [0, 0, 1, 1, 2, 2])
Just 1
>>> lookupLEIH 0 (fromList [0, 0, 1, 1, 2, 2])
Just 0
>>> lookupLEIH (-1) (fromList [0, 0, 1, 1, 2, 2])
Nothing

lookupGEIH :: Int -> IntHeap -> Maybe Int Source #

O(log n)

>>> lookupGEIH 1 (fromList [0, 0, 1, 1, 2, 2])
Just 1
>>> lookupGEIH 2 (fromList [0, 0, 1, 1, 2, 2])
Just 2
>>> lookupGEIH 3 (fromList [0, 0, 1, 1, 2, 2])
Nothing

nullIH :: IntHeap -> Bool Source #

O(1)

sizeIH :: IntHeap -> Int Source #

O(n)

>>> sizeIH (fromList [0, 0, 1, 2])
4
>>> sizeIH emptyIH
0

findMinIH :: IntHeap -> Int Source #

O(min(n,W))

>>> findMinIH (fromList [0, 0, 1, 2])
0
>>> findMinIH emptyIH
*** Exception: findMin: empty map has no minimal element

findMaxIH :: IntHeap -> Int Source #

O(min(n,W))

>>> findMaxIH (fromList [0, 0, 1, 2])
2
>>> findMaxIH emptyIH
*** Exception: findMax: empty map has no maximal element

deleteMinIH :: IntHeap -> IntHeap Source #

O(min(n,W))

>>> deleteMinIH (fromList [0, 0, 1, 2])
[0,1,2]
>>> deleteMinIH emptyIH
*** Exception: updateMinWithKey Nil

deleteMaxIH :: IntHeap -> IntHeap Source #

O(min(n,W))

>>> deleteMaxIH (fromList [0, 1, 2, 2])
[0,1,2]

>>> deleteMaxIH emptyIH
*** Exception: updateMaxWithKey Nil

deleteFindMinIH :: IntHeap -> (Int, IntHeap) Source #

O(min(n,W))

>>> deleteFindMinIH (fromList [0, 0, 1, 2])
(0,[0,1,2])
>>> deleteFindMinIH emptyIH
deleteFindMin: empty map has no minimal element

deleteFindMaxIH :: IntHeap -> (Int, IntHeap) Source #

O(min(n,W))

>>> deleteFindMaxIH (fromList [0, 1, 2, 2])
(2,[0,1,2])

>>> deleteFindMaxIH emptyIH
deleteFindMax: empty map has no maximal element

minViewIH :: IntHeap -> Maybe (Int, IntHeap) Source #

O(min(n,W))

>>> minViewIH (fromList [0, 0, 1, 2])
Just (0,[0,1,2])

>>> minViewIH emptyIH
Nothing

maxViewIH :: IntHeap -> Maybe (Int, IntHeap) Source #

O(min(n,W))

>>> maxViewIH (fromList [0, 1, 2, 2])
Just (2,[0,1,2])

>>> maxViewIH emptyIH
Nothing

splitIH :: Int -> IntHeap -> (IntHeap, IntHeap) Source #

O(min(n,W))

>>> splitIH 1 (fromList [0, 0, 1, 2])
([0,0],[2])
>>> splitIH 0 (fromList [0, 0, 1, 2])
([],[1,2])
>>> splitIH (-1) (fromList [0, 0, 1, 2])
([],[0,0,1,2])

splitLookupIH :: Int -> IntHeap -> (IntHeap, [Int], IntHeap) Source #

O(min(n,W))

>>> splitLookupIH 1 (fromList [0, 0, 1, 2])
([0,0],[1],[2])
>>> splitLookupIH 0 (fromList [0, 0, 1, 2])
([],[0,0],[1,2])
>>> splitLookupIH (-1) (fromList [0, 0, 1, 2])
([],[],[0,0,1,2])