# 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:

- 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.

- 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?

- Structural property? OK.
- Ordering property? OK.

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.