Heaps
Another type of special binary tree is called a heap. In order to understand what a heap is, we must first define a complete and full binary tree. In a full binary tree, all nodes are either a parent with two children, or a leaf. In a complete binary tree, all the levels except the last must be completely filled. In the last level, all nodes must be filled in from the left side, without spacing between them, however, it does not have to be filled to the end.
A heap is a complete binary tree, which is partially ordered with either the max-heap or min-heap properties. That is, if a heap is a max-heap, then the children of every node have a value less than that node. In a min-heap, the children of every node are greater than the node itself. With such a setup, the main root always has either the highest or lowest value in the tree. For demonstration purposes, we will show how to implement a max-heap, as it also an important part of the HeapSort algorithm, which will be covered later. [It is easy to change to code to work as a min-heap by changing the relational operators between node values]. A max-heap usually used for maintaining priority queues. Priority queues store values and release the object with the highest "priority" (or value) when needed. For instance, a value is associated with a particular task in a program, put into such a structure, and then executed based on its position.
Since a heap must conform to the complete tree property, simple formulae can be libraryeloped to find the logical position of a node's children and parent given the position of the node itself. It is therefore very easy and efficient to implement a heap using arrays, and is done so most of the time, even if dynamic memory allocation is available.
In an array implementation, we must allocate a certain amount of memory space that may be used for the heap. The space may not be used up, and is therefore a waste of memory. Other times, we may need to add more nodes to the heap than the allocated memory allows for. However, we usually allocate more space than we think may be required in order to insure the heap is usable. If we have a tree of very large structures, this space can be significant. However, this is the price we always pay for greater efficiency. It should noted though, that we no longer have three pointers for every tree node (left, right, parent), which took up a lot of space in the dynamic memory implementation. The logical position of a node in a heap corresponds to the index of the node's array position, thereby making it very easy to access any node. A generic implementation is shown below.
template <class ItemType>
//default constructor - initialize private variablesconst int MAX_SIZE = 100; //the maximum amount of elements our heap should have. This may be changed to any number so long as memory permits, depending on how the heap will be used.
class Heap
{
public:
Heap();
int left(int) const;
int right(int) const;
int parent(int) const;
void insert(const ItemType&);
ItemType remove_max();
bool IsEmpty() const;
bool IsFull() const;
int count() const;
ItemType value(int) const;
private:
ItemType array[MAX_SIZE];
int elements; //how many elements are in the heap
void ReHeap(int);
};
template <class ItemType>
Heap<ItemType>::Heap()
{
elements = 0;
}
The left(), right(), and parent() functions return the index positions of a node's children and parent. Since the index position of each element correspond to their logical position in the heap, the functions use simple formulae that are derived by observing the heap structure.
template <class ItemType>
template <class ItemType>template <class ItemType>
int Heap<ItemType>::left(int root) const
{
assert(root
}
int Heap<ItemType>::right(int root) const
{
assert(root < (elements-1)/2); //does a right child exist?
return (root * 2) + 2;
}
int Heap<ItemType>::parent(int child) const
{
assert(child != 0); //main root has no parent
return (child - 1) / 2;
}
The insert() function accepts the new item value as its parameter. It works by inserting the new item at the end of the heap, and swapping positions with the parent, if the parent has a smaller value than the item. The new item continues to travel up the heap, swapping its position with its new parents until the item's parent is larger than it.
template <class ItemType>
void Heap<ItemType>::insert(const ItemType &item)
{
assert(!IsFull());
array[elements] = item; //elements represents the array position after the last, since indexing starts with 0
int new_pos = elements; //index of the new item
elements++; //update the amount of elements in heap
while((new_pos != 0) && (array[new_pos] > array[parent(new_pos)])) //loop while the item has not become the main root, and while its value is less than its parent
{
swap(array[new_pos],array[parent(new_pos)]); //swap the value of item with its lesser parent
new_pos = parent(new_pos); //update the item's positions
}
}
The remove_max() removes the item with the highest priority and returns its value. The item is swapped with the last item, and elements is updated to one less.
Notice the item is not physically deleted, it will remain as part of the array. It will not be part of the heap since elements is updated, and the heap goes only as far as (elements - 1).
The new root may not have the largest priority, therefore the ReHeap() function is then used to insert the new root into its proper position, thus conserving the heap property.
template <class ItemType>
ItemType Heap<ItemType>::remove_max()
{
assert(!IsEmpty());
elements--; //update the amount of elements in heap
if(elements != 0) //if we didn't delete the root
{
swap(array[0],array[elements]);
ReHeap(0);
}
return array[elements];
}
The ReHeap() function checks of either of root's children are bigger than it, in which case the bigger child is swapped with root. The process is then continued using recursion, on root's new children. The function stops when root is bigger than both of its children.
template <class ItemType>
void Heap<ItemType>::ReHeap(int root)
{
int child = left(root);
if((array[child] < array[child+1]) && (child < (elements-1))) //if a right child exists, and it's bigger than the left child, it will be used
child++;
if(array[root] >= array[child]) //if root is bigger than its largest child, stop.
return;
swap(array[root],array[child]); //swap root and its biggest child
ReHeap(child); //continue the process on root's new children
}
The rest of our member functions are east to implement.
template <class ItemType>
template <class ItemType<
template <class ItemType>template <class ItemType>
int Heap<ItemType>::count() const
{
return elements;
}
ItemType Heap<ItemType>::value(int pos) const
{
assert(pos < elements); //is pos a valid index in the heap
return array[pos];
}
bool Heap<ItemType>::IsEmpty() const
{
return (elements == 0);
}
bool Heap<ItemType>::IsFull() const
{
return (elements == MAX_SIZE);
}