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);            // Constructor
    ~heap(void);           // Destructor

    void add(int item);    // Adds an item
    int  remove(void);     // Removes largest node

  private:
    int data[MAX_NODES];     // The actual data
    int nodeNum;             // Number of nodes

    void shiftUp(int node);   // A helper function
    void shiftDown(int node); // A helper function
};

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