FIFO QUEUES > class Queue q where > empty :: q a > isEmpty :: q a -> Bool > snoc :: q a -> a -> q a > head :: q a -> a > tail :: q a -> q a We implement a queue by a pair of lists: one containing the elements in the front of the queue; the other containing the elements at the rear of the queue in reverse order. > data BQueue a = BQueue [a] [a] The front part of the queue should always be non-empty unless the whole queue is empty. > checkf :: BQueue a -> BQueue a > checkf (BQueue [] r) = BQueue (reverse r) [] > checkf q = q > instance Queue BQueue where > empty = BQueue [] [] > isEmpty (BQueue f r) = null f -- if f is empty, so is r > snoc (BQueue f r) x = checkf (BQueue f (x:r)) > head (BQueue (x:f) r) = x > tail (BQueue (x:f) r) = checkf (BQueue f r) Amortized analysis using the potential method. Define a potential for every queue: phi :: BQueue a -> Int phi (BQueue f r) = length r The amortized cost of any operation is the actual cost plus the change in the potential function. If an operation turns a queue q into q', then the amortized cost is: amortizedCost = actualCost + phi(q') - phi(q) It's easy to verify that the amortized cost of all operations is O(1). Therefore a sequence of n operations has cost O(n). BINARY COUNTERS > type Counter = [Bool] A binary counter is simply a number in binary notation with a function to increase it by one. The Boolean values False and True are used for the binary digits 0 and 1. The number is written in inverse order: the head of the list is the least significant digit. Functions to traslate between integers and counters. Just to show the interpretation of the counter: we do not use them in code, but only use the increment operation. > intCounter :: Integer -> Counter > intCounter 0 = [] > intCounter x = odd x : intCounter (x `div` 2) > countInteger :: Counter -> Integer > countInteger [] = 0 > countInteger (b:bs) = if b then 1+2*countInteger bs else 2*countInteger bs > increment :: Counter -> Counter > increment [] = [True] > increment (False:bs) = True : bs > increment (True:bs) = False : increment bs The worst case cost of an increment operation is equal to the length of the binary counter. The worst case is when all values in the counter are 1 (True). So the worst case cost of n increment operations is O(n . log n), since the length of the counter is logaritmic in the number of increments. We can get a much better estimate of the cost of n increment operations by using amortized analysis with the potential method. We define the potential to be the number of unit digits: phi :: Counter -> Nat phi bs = number of True values in bs phi is always positive and is 0 on the empty counter. The actual cost of an increment operation is t+1, where t is the number of leading True values in the counter: all the leading True values are reset to False and the next False is changed to True (or we add a True if we reached the end of the list). The change of potential is -t+1 because we changed t True values to False and added a new True value. phi(increment bs) - phi(bs) = -t+1 So the amortized cost is: amortizedCost = actualCost + phi(increment bs) - phi(bs) = t+1 -t+1 = 2 BINOMIAL HEAPS In the file on binomial heaps we prove that all heap operations cost O(log n) time, where n is the number of elements in the heap. In particular, the insert operation has worst case complexity O(log n). Therefore the cost of m operations is O(m.log n). We can now prove that insert has amortized complexity O(1). Define the potential as phi :: BHeap a -> Nat phi (h) = length h Remember that a binomial heap is a list of binomial trees, the potential is the number of trees in the heap. If the heap contains n elements, then the number of trees is equal to the number of ones in the binary expansion of n. The situation is similar to that of a binary counter. First of all, "insert" creates a new tree with the element to be inserted and puts it into the heap by using insTree. This increases the number of trees by 1. Let k be the number of calls to "link" in the execution of the "insert" operation. Every link step turns two trees into one, therefore decreases the potential by one: phi (insert a h) - phi h = 1-k The actual cost of "insert" is k+1, since every link takes O(1). The amortized cost is then: amortizedCost = actualCost + phi(insert a h) - phi(h) = k+1+1-k = 2 Be careful: this shows that a sequence of n "insert" operations costs O(n) time. This assumes that we are only using "insert" to modify the heap. The other operations that modify the heap (deleteMin and merge) don't have constant amortized complexity, but they still have logarithmic amortized complexity.