Outline

• exam review
• binary tree traversal
• heaps
• heap storage in arrays
• heap insertion and removal
• priority queues
• priority queues implementation

binary tree traversal

• binary tree traversal is easy using recursion:
  • preorder: visit the root node, then recursively visit the left subtree, then recursively visit the right subtree
  • inorder: recursively visit the left subtree, then visit the root node, then recursively visit the right subtree
  • postorder: recursively visit the left subtree then recursively visit the right subtree, then visit the root node
• this is hard using just loops
• a stack is needed to keep track of where we are in the tree
• for example, for preorder traversal, I would visit (print, etc) the current node, push onto the stack the right subtree, then visit the left subtree
• when I reach a leaf node, I pop the next subtree off the stack, and continue from that node
• inorder and postorder are more complex
• this can also be done without a stack if the nodes have parent references, and then it is similar to backtracking

Heaps

• a heap is a binary tree (but not a binary search tree)
• in which each node has a value less than its children (min heap)
• or a value greater than its children (max heap)
• this is the heap property
• so nodes in a heap are not sorted

heap requirements

• as well as the heap property of each node needing to be less (greater) than its children,
• in a heap, all leaves at maximum level d_max are to the left of all the other leaves, which are at level d_max - 1
• in-class exercise: is this a max or a min heap?
• such a binary tree (all leaves at max level to the left of all other leaves, which are at level d_max - 1) is called a complete binary tree
• a heap is always a complete binary tree
• a complete binary tree is always balanced, so that a complete binary tree of n nodes has level O(log n)
• in-class exercise: in what sense can I say that a complete binary tree is balanced?

heap storage

• any complete binary tree, including any heap, can be conveniently stored in an array:
  • element 0 of the array stores the root
  • elements 1 and 2 of the array store the nodes at level 1
  • elements 3, 4, 5, and 6 of the array store the nodes at level 2
  • nodes at level d are stored in array elements 2^d-1...2^d+1 - 2
• conveniently, there is no need to store any pointers: a node stored in array element i has:
  • its parent in array element (i - 1) / 2
  • its left child (if any) in array element 2i + 1
  • its right child (if any) in array element 2i + 2
• since a heap is a complete binary tree, the right child can only be present if the left child is also present (there may be one left child leaf node that does not have a right sibling)

in-class exercises

• store this heap into an array
• which of the following arrays store max heaps, min heaps, or neither?

  index     0   1   2   3   4   5   6   7   8   9
  array 1   0   1   2   0   4   5   6   7   8   9
  array 2   9   8   7   6   5   4   3   2   1   0
  array 3   5   5   5   6   6   6   6   7   7   1
  array 4   9   3   9   2   1   6   7   1   2   1
  array 5   8   7   6   1   2   3   4   2   1   2
  

Heap insertion

• the two heap requirements must be maintained when adding to a heap
• to maintain the complete binary tree property, the new node must be added to the right of all nodes at level d_max
• or, if there already are 2^(d_max) nodes at that level, the new node should be inserted all the way to the left, making the tree deeper by one level
• either way, the new value is inserted in the array just after all elements already in the array
• now the tree is complete, but may not have the heap property
• to check, compare the node with the parent, and swap the two if needed to maintain the heap property
• continue with the parent's parent, all the way to the root if necessary
• now the complete binary tree also obeys the heap property

Max heap deletion

• the largest node is at the root of the heap
• that node is deleted, and replaced with the bottommost, rightmost node
• the remaining tree is complete, but may not have the tree property
• if the root node is less than either of its children, it is swapped with the largest of its children
• the operation continues with the new node
• now the complete binary tree also obeys the heap property
• similarly for min heaps

in-class exercises

• insert into a heap the following values:
  1 9 77 14 3 55 66 7 8
• remove from the heap each of the elements in turn

priority queues

• the queues studied so far were strictly FIFO
• that means objects were returned in the order inserted
• in the real world, often have priorities, e.g.:
  • at airport check-in, there is a special line for first-class passengers
  • if any first-class passengers are waiting, they are handled first
  • only if no first-class passengers are waiting, only then the other passengers can check-in
• likewise in the emergency room at a hospital or after a disaster
• the process of determining which patients should be seen first is called triage (a medical term, not a computer science term)

priority queue implementations

• linked list: objects are inserted in the proper place in the list (linear time), objects are returned from the front of the list (constant time)
• array: objects are inserted in the proper place in the array, with all other objects shifted to make room (linear time), objects are returned from the front of the array, with all other objects shifted down (linear time), or maintained as a circular array (constant time)
• binary search tree: objects are inserted into the binary search tree, using the priority as the key (log or linear), objects are removed from the rightmost node of the tree (log or linear)
• heap: objects are inserted into the heap using the priority as the key (log time), and removed from the top of the heap (log time)