In this document we review the important ideas behind

1. Embedding binary trees in arrays
2. The definition and use of Heap data structures for finding the minimum (maximum) element of a set.

Array embedded binary trees

Binary trees can be efficiently stored in arrays by using an encoding that stores tree elements at particular indexes in the array. One can compute the indexes of that tree nodes left-child, right-child, and parent node using a simple formula.

We can envision this process by the following picture.

Trees as arrays with implicit links

Several invariants must hold for this to work.

• The array must be larger than the number of nodes in the tree.
• The tree must be balanced. Either a full-tree or a complete-tree.
• The array must be zero indexed (the first slot must have index zero) or the formulae won't work out.
• An extra variable indicating the last slot in the array that is in use. This index notes the rightmost node in the last rank of the tree. This would be index 9 in the picture above, indicating the node labelled E.

The formulae for computing the tree child and parent relationships are:

• root = 0
  

• left_child  i = i*2 + 1
  

• right_child i = i*2 + 2
  

• parent i | even i = (i `div` 2) - 1
           | odd i  = i `div` 2
  			  

Heaps

• A Heap is a data structure used to efficiently find the smallest (or largest) element in a set.
• Min-heaps make it easy to find the smallest element.Max-heaps make it easy to find the largest element.
• Heaps are based upon trees. These trees maintain the heap property.
  1. The Heap invariant. The value of Every Child is greater than the value of the parent. We are describing Min-heaps here (Use less than for Max-heaps).
• The trees must be mostly balanced for the costs listed below to hold.
• Access to elements of a heap usually have the following costs.
  1. The cost to find the smallest (largest) element takes constant time.
  2. The cost to delete the smallest (largets) element takes time proportional to the log of the number of elements in the set.
  3. The cost to add a new element takes time proportional to the log of the number of elements in the set.
• Heaps can be implemented using arrays (using the tree embedding described above) or by using balanced binary trees. In class we implemented heaps both ways. We used leftist trees to ensure balance.
• Trees with the leftist property have the following invariant.
  1. The leftist invariant. The rank of every left-child is equal to or greater than the rank of the cooresponding right-child. The rank of a tree is the length of the right-most path.
• Heaps form the basis for an efficient sort called heap sort that has cost proportional to n*log(n) where n is the number of elements to be sorted.
• Heaps are the data structure most often used to implement priority queues.

Array Based Trace

A trace of adding a sequence of elements to an empty Max-heap. Note how the tree is always either a full or complete tree. Note how the last variable always points to the index of the last node of the tree.

empty heap

add 3
 3


 0   1   2   3   4   5   6    index
[3,-99,-99,-99,-99,-99,-99]   values  last = 0

add 6
 +-6
 3


 0 1   2   3   4   5   6    index
[6,3,-99,-99,-99,-99,-99]   values  last = 1
add 9
 +-9-+
 3   6


 0 1 2   3   4   5   6    index
[9,3,6,-99,-99,-99,-99]   values  last = 2

add 7
   +-9-+
 +-7   6
 3


 0 1 2 3   4   5   6    index
[9,7,6,3,-99,-99,-99]   values  last = 3

delete largest element
 +-7-+
 3   6


 0 1 2 3   4   5   6    index
[7,3,6,9,-99,-99,-99]   values  last = 2

add 8
   +-8-+
 +-7   6
 3


 0 1 2 3   4   5   6    index
[8,7,6,3,-99,-99,-99]   values  last = 3

add 2
   +---8-+
 +-7-+   6
 3   2


 0 1 2 3 4   5   6    index
[8,7,6,3,2,-99,-99]   values  last = 4

add 56
   +---56---+
 +-7-+    +-8
 3   2    6


  0 1 2 3 4 5   6    index
[56,7,8,3,2,6,-99]   values  last = 5

delete largest element
   +---8-+
 +-7-+   6
 3   2


 0 1 2 3 4  5   6    index
[8,7,6,3,2,56,-99]   values  last = 4

Leftist-invariant Tree Based Trace

A trace of adding a sequence of elements to an empty Min-heap. Note how the tree always maintains the leftist invariant.

add 5

 5


add 8

 +-5
 8


add 3

   +-3
 +-5
 8


add 9

   +-3-+
 +-5   9
 8


add 4

   +-3---+
 +-5   +-4
 8     9


add 2

     +-----2
   +-3---+
 +-5   +-4
 8     9


add 3

     +-----2-+
   +-3---+   3
 +-5   +-4
 8     9


delete min element

   +-3-----+
 +-5     +-3
 8     +-4
       9


delete min element

   +-3---+
 +-4   +-5
 9     8


delete min element

 +-4---+
 9   +-5
     8


add 1

   +-----1
 +-4---+
 9   +-5
     8


add 4

   +-----1-+
 +-4---+   4
 9   +-5
     8


delete min element

 +-4-----+
 9     +-4
     +-5
   8

Back to the class web-page.