**Heap
Trees, Part 1**

(Up to Basic
Computer Science : Data Trees)

[Part 1] [Part
2]

**Heap Trees **(or just **Heaps**) are a form of binary tree
in which each node is greater than or equal to **both** of its
children. Thus, the largest element in the entire tree is always
the root of the tree.

Although it is not necessary, it is often quite useful to define
the heap as both **full** and **dense**. Fullness and density
are qualities that both apply to binary trees and most trees in
general as well. In a** full binary tree,** all of the nodes
with less than two children (so, the nodes whose branches aren't
"filled") in the bottom two levels. A binary tree is **dense**
when it is a full tree such that, in the second to last level, all
nodes with two children will be to the left of a node with one child,
and a node with only one child will come to the left of the nodes
with no children. The final requirement for density is that there
is no more than one node in the second to last level that has only
one child, and that one child must be the node's left child. Density
is also sometimes called **leftness** (because all of the nodes
in the last level are shuffled to the left).

In addition, the heap is usually defined so that only the **largest**
element (that is, the root) will be removed at a time. This makes
the heap useful for scheduling and prioritizing. In fact, one of
the two main uses of the heap is as a **priority queue**, which
helps systems decide what to do next.

Implementing and programming this structure is not as difficult
as it was with a normal binary search tree because the denseness
and fullness allow us to conveniently represent the heap with an **array**. In a **0-indexed** array (the first element has
the index 0), a node at the index n has
a parent node at (n-1)/2, rounded down.
This is the appeal of the heap: it is fast, efficient, and requires
minimal storage space.

So, take a look at the structure outlined below:

**class** heap {
**public**:
heap(**void**);
~heap(**void**);
**void** add(**int** item);
**int** remove(**void**);
**private**:
**int** data[MAX_NODES];
int nodeNum;
**void** shiftUp(**int** node);
**void** shiftDown(**int** node);
};

Most of this is pretty simple to comprehend, but the private
section requires a bit of explanation. The shiftUp()
and shiftDown() functions are needed to
implement the add() and remove()
functions easily. The node parameter passed
to both helper functions are the index to the node that you wish
to shift. The shiftUp() function moves
the given node as high as possible in the heap tree without violating
any rules. shiftDown() does the exact
opposite: it tries to move the node as far down as possible. Together,
these functions allow you to shift a node into place.

So, for the add() function, just tack
the item onto the end of the heap (the
end of the array) and call shiftUp() on
it. To implement remove(), just take out
the root of the tree and replace it with the last element. Then,
just call shiftDown() on the new root
node to shift it into place.

Other than as a priority queue, the heap has one other important
usage: **Heap sort**.

**Heap Trees Part 2: Heap Sort**