Solutions week 5 - Sorting

Stacks and queues

1, 2, 3, 4

Download the following file with example implementations.

5

Consider an empty queue and a full queue. Both queues will have rear == (front - 1) % capacity. Thus the code for size cannot tell these two cases apart.

One trick to fix this is to alter the queue constructor to allocate an array one element bigger than necessary. That way the array never gets full (provided the client doesn’t try to fill the queue beyond its capacity) and the trick for finding the size works.

6

See CircularBoundedBuffer.java.

Binary heaps

1a

Let the element ordering of the heap order property be >= instead of <=.

1b

See HeapPQ.java.

2

Inserting 6, 8, 4, 7, 2, 3, 9, 1, 5.

inserting 6
[6]
 6

inserting 8.
[6,8]
  6
 8

inserting 4 and restoring the heap invariant.
[6,8,4] -> [4,8,6]
  6          4
 8 4        8 6

inserting 7 and restoring the heap invariant.
[4,8,6,7] -> [4,7,6,8]
   4            4
  8 6          7 6
 7            8

inserting 2 and restoring the heap invariant.
[4,8,6,7,2] -> [4,2,6,7,8] -> [2,4,6,7,8]
    4              4              2
  8   6          2   6          4   6
 7 2            7 8            7 8

inserting 3 and restoring the heap invariant.
[2,4,6,7,8,3] -> [2,4,3,7,8,6]
     2                2
  4    6           4    3
 7 8  3           7 8  6

inserting 9.
[2,4,3,7,8,6,9]
     2
  4    3
 7 8  6 9

inserting 1 and restoring the heap invariant.
[2,4,3,7,8,6,9,1] -> [2,4,3,1,8,6,9,7] -> [2,1,3,4,8,6,9,7] -> [1,2,3,4,8,6,9,7]
      2                    2                    2                    1
   4     3              4     3              1     3              2     3
  7 8   6 9            1 8   6 9            4 8   6 9            4 8   6 9
 1                    7                    7                    7

inserting 5.
[1,2,3,4,8,6,9,7,5]
        1
    2       3
  4   8   6   9
 7 5
Inserting 6, 8, 4, 7, 2, 3, 9, 1, 5 using buildHeap.
if indexing from 0: loop over interval [⌊N/2⌋ − 1, 0].
if indexing from 1: loop over interval [⌊N/2⌋, 1].

initial state before starting buildheap.
[6, 8, 4, 7, 2, 3, 9, 1, 5]
        6
    8       4
  7   2   3   9
 1 5

after executing buildHeap(4)
[6, 8, 4, 1, 2, 3, 9, 7, 5]
        6
    8       4
  1   2   3   9
 7 5

after executing buildHeap(3)
[6, 8, 3, 1, 2, 4, 9, 7, 5]
        6
    8       3
  1   2   4   9
 7 5

after executing buildHeap(2) iteration 1
[6, 1, 3, 8, 2, 4, 9, 7, 5]
        6
    1       3
  8   2   4   9
 7 5

after executing buildHeap(2) iteration 2
[6, 1, 3, 5, 2, 4, 9, 7, 8]
        6
    1       3
  5   2   4   9
 7 8

after executing buildHeap(1) iteration 1
[1, 6, 3, 5, 2, 4, 9, 7, 8]
        1
    6       3
  5   2   4   9
 7 8

after executing buildHeap(1) iteration 2
[1, 2, 3, 5, 6, 4, 9, 7, 8]
        1
    2       3
  5   6   4   9
 7 8

3

data BTree a = Node (BTree a) a (BTree a)
             | Empty

isComplete :: BTree a -> Bool
isComplete tree = let (complete, _, _) = helper tree
                   in complete
    where helper :: BTree a -> (Bool, Int, Bool)
          helper Empty = (True, 0, True)
          helper (Node Empty _ Empty) = (True, 1, True)
          helper (Node Empty _ right@(Node _ _ _)) = (False, 1 + rightHeight, False)
            where (_, rightHeight, _) = helper right
          helper (Node left@(Node _ _ _) _ Empty) = (leftHeight == 1, 1 + leftHeight, False)
            where (_,  leftHeight,  _)  = helper left
          helper (Node left _ right) = (complete, height, bottomFull)
            where (_,             leftHeight,  leftBottomFull)  = helper left
                  (rightComplete, rightHeight, rightBottomFull) = helper right
                  complete   = leftBottomFull && rightComplete && (leftHeight == rightHeight)
                  height     = 1 + max leftHeight rightHeight
                  bottomFull = leftBottomFull && rightBottomFull

4

Just use a integer to save the minimum. We never remove the minimum :)

Menu