What is a heap?

It is a binary tree with the following properties:

•    Property 1: it is a complete binary tree
•    Property 2: the value stored at a node is greater or equal to the  values stored at the children 

   What is a heap? (cont.)

   Largest heap element

       From Property 2, the largest value of the heap is always stored at the root 

Heap Specification

template<class ItemType>

struct HeapType {

  void ReheapDown(int, int);

  void ReheapUp(int, int);

  ItemType *elements;

  int numElements; // heap elements

};