3. Abstract Type HEAP (Section 8.4)

A Heap is a binary tree with two special properties

Ordering Property

The value in a node is smaller than all the values in the node's subtrees.

This is very different than a binary search tree!

Note that this property makes no distinction between `left' and `right'. All the following trees have this property:

Incidentally, heaps can also be defined with the opposite ordering property: the value in each node is larger than all the values in its subtrees.

Structural Property

All the levels are full, except perhaps the bottom level, and all the nodes in the bottom level are as far to the `left' as possible.

A level is full if there are no `missing nodes' at the level - there are 2**L nodes in level L.

This structural property could be rephrased: the only nodes that can have an empty subtree are ones in the bottom level (by definition these have 2 empty subtrees) and the rightmost nodes in the next-to-bottom level.

A tree that has this property is called a complete tree. There are two motives for restricting ourselves to complete trees:

  1. In a complete tree Height = O(logN). As we'll see, our Heap operations are O(Height), so by restricting ourselves to complete trees, we get O(logN) operations.

  2. complete trees have certain advantages over general binary trees in some implementations (we'll see an example later).

Example

Although all 3 of the above trees have the ordering property, only one of them satisfies the structural requirement. Which one?

Answer: The middle one - that is the only one of those trees that is a heap.

Is this a heap?
It has both properties, so yes it's a heap.

It looks pretty disorganized: the smallest value must always be in the root, but the largest value could be in any leaf! Similar values are not collected together in any convenient location. Note that 25 is at a lower level than 30 (but, of course, not in 30's subtrees). However, there is more structure than immediately meets the eye.