A heap is similar to a binary search tree. It differs in the
following ways :
 A heap is sorted in a less strict way then a binary search tree
With a binary search tree a node's larger child is on the
right hand side and the smaller one on the left. With a heap,
a node's children are always less than or equal to it and the right child
isn't always the larger one. This means that the root of the
tree is always the largest item unlike a binary tree.
 Binary search trees come in a number of shapes, while a heap is
always a complete binary tree.
A heap is a complete binary tree: That is empty
or Whose root contains a value >= to the key value of
each of its children and
 Whose root has heaps as its
subtrees.
A Heap
What are heaps used for?
Priority Queues
A priority queue is a queue of items sorted by their priority.
Priority queue operations are exactly the same as operations on
heaps. The priority value in a priority queue corresponds to a
node's search key in a heap. Thus a heap can be used directly has
a priority queue.
Heap sort
As the name implies a heap sort uses a heap. The heap sort is an efficient
sorting algorithm that has a running time of O (N * log N) in both the
average and worst case. This is faster than the worst case of a
quick sort which is O (N^{2}).
Huffman coding
Huffman coding is a way of compressing data. Heaps help in the implementation
of this algorithm which will be discussed in an upcoming article.
The Implementation
In VB references to object can be used to link the nodes of a heap
or an array can be used. Arrays where used in this implementation
because they can be dynamically resized in
Visual Basic giving the main advantage of the reference option with a
lower memory overhead because references don't need to be kept.
The items in this heap are ordered by their key. The array
which holds each node in the heap is of type HeapItem. The definition
of HeapItem is shown below:
Private Type HeapItem
Key As Variant
Data As Variant
End Type

The Heap class has the following subs, functions and properties:
 Add (Key, Data)
Adds an item at it's correct position in the array based on the
key.
 Remove
Returns and removes the root of the heap. The root is the
largest item in the tree and is stored at position 0 in the array.
 Count
The number of items in the heap.
The Add sub works by:
 Inserting the new item after the last item in the heap.
 Finding the parent of the last item in the heap
using
Parent = (NewItemItemIndex  1) / 2
 Trickling the item up to its proper position by: (Loop)
 Moving the new item up the tree by swapping it with it's
parent, if it is larger than it's parent which is at (NewItemItemIndex  1) / 2.
 Incrementing Size by 1
Below is a diagram of a heap structure and how it would look in an
array.
Heap 
Index 
Value 
0 
9 
1 
8 
2 
7 
3 
3 
4 
2 
5 
5 
Representation in array

Say you wanted to add the value 16 to the heap. You would:
Array before entering loop 
After first loop 
After second loop
item is at it's correct
position.

Resize array and place new item at the end. 
Swap item 6 with it's parent item 2. 
Swap item 2 with it's parent item 0. 
Index 
Value 
0 
9 
1 
8 
2 
7 
3 
3 
4 
2 
5 
5 
6 
16 *NewItem 
Parent = 2 = (6  1) / 2
* Computer rounds down 
Index 
Value 
0 
9 
1 
8 
2 
16 *NewItem 
3 
3 
4 
2 
5 
5 
2 
7 
Parent = 0 = (2  1) / 2 
Index 
Value 
0 
16 *NewItem 
1 
8 
2 
9 
3 
3 
4 
2 
5 
5 
2 
7 




The child item is shown in italics and it's parent that it is
swapped with in bold.
The Remove function works by:
 Replacing the root that is Item(0) with the item at the end of the
array.
 Trickling the item placed in the root down to it's correct
position.
For example to remove item 16:
Before deletion 
Copy item 6 to 0 and resize the array. This leaves a complete binary tree. But in this case not a heap
because 7 is out of place. This is known as a semiheap. 
Trickle 7 down to correct position by turning the semiheap into a
heap. 
Index 
Value 
0 
16 
1 
9 
2 
8 
3 
3 
4 
2 
5 
5 
6 
7 

Index 
Value 
0 
7 
1 
9 
2 
8 
3 
3 
4 
2 
5 
5 

Index 
Value 
0 
9 
1 
7 
2 
8 
3 
3 
4 
2 
5 
5 


Place last node at root
and resize array. 

In this example the last action happens one time but it could take
more than one operation to trickle the item down to it's correct
position. In the class the private sub RebuildHeap is used to
trickle the items down.
Code
Option Explicit
Private Type HeapItem
Key As Variant
Data As Variant
End Type
Dim Items() As HeapItem
Dim lSize As Long ' Number of items in the heap
Public Property Get Count() As Long
Count = lSize
End Property
Private Sub RebuildHeap(ByVal Root As Long)
' Converts a semiheap rooted at index Root into a heap
' Recursively trickle the item at index Root down to
' its proper position by swapping it with its larger
' child, if that child is larger then the item.
' If the item is a leaf, nothing needs to be done
Dim ChildIndex As Long
Dim RightChildIndex As Long
' If the root is not a leaf and the root's value is less than the larger
'of the values of the root's children.
ChildIndex = 2 * Root + 1 ' Index of root's left child, if any
If ChildIndex < lSize Then
' Root is not a leaf.
' So it has a leaf child at child
RightChildIndex = ChildIndex + 1 ' Index of right child, if any.
' If root has a right child, find larger child
If (RightChildIndex < lSize) And _
(Items(RightChildIndex).Key > Items(ChildIndex).Key) Then
ChildIndex = RightChildIndex ' Index of larger child
End If
' If the root's value is smaller than the value
' in the larger child, swap values
If Items(Root).Key < Items(ChildIndex).Key Then
Dim Temp As HeapItem
Temp = Items(Root)
Items(Root) = Items(ChildIndex)
Items(ChildIndex) = Temp
' Transform new subtree into a heap
RebuildHeap ChildIndex
End If
End If
End Sub
' Returns and removes the
' item with the largest key in the heap.
' The largest item will be at
' the heap's root.
Public Function Remove() As Variant
'Swaps the last item in the heap with the root
'and trickles it down to its proper position.
If lSize > 0 Then
Remove = Items(0).Data
lSize = lSize  1
Items(0) = Items(lSize)
RebuildHeap 0
ReDim Preserve Items(lSize)
Else
Remove = Empty ' Heap empty
End If
End Function
' Adds an item and the key used
' to sort the heap by.
Public Sub Add(ByVal Key As Variant, ByVal Data As Variant)
'Inserts the new item after the last item in the heap
'and trickles it up to its proper position.
'Place the new item at the end of the heap
ReDim Preserve Items(lSize) ' Make room for the new item.
Items(lSize).Key = Key
Items(lSize).Data = Data
Dim Place As Long, Parent As Long
' Trickle new item up to its proper position
Place = lSize
Parent = (Place  1) / 2
Do While Parent >= 0 And (Items(Place).Key > Items(Parent).Key)
' swap Items(Place) and Items(Parent)
Dim Temp As HeapItem
Temp = Items(Parent)
Items(Parent) = Items(Place)
Items(Place) = Temp
Place = Parent
Parent = (Place  1) / 2
Loop
lSize = lSize + 1
End Sub 
Example of using the heap class
Items are returned "Cat", "Dog", "Bat",
"Apple".
Dim Heap As clsHeap
Set Heap = New clsHeap
With Heap
.Add 2, "Bat"
.Add 1, "Apple"
.Add 5, "Cat"
.Add 4, "Dog"
Do While .Count > 0
MsgBox .Remove
Loop
End With 
Download Heap Class
Terms used
Binary Tree  A tree structure were each node can have up to
two children.
Binary Search Tree  A binary tree that is sorted so that all
larger items are on the right and smaller on the left. For
example:
Height. The number of nodes on the longest path from the root
to a leaf. The above tree has a height of 3.
A Full Binary Tree has a height h with no missing nodes.
All leafs are at level h and all other nodes have two children.
A Complete Binary Tree has a height h that is full to level
h  1 and has level h filled in from left to right. The above tree
is a complete binary tree.
References
Frank M. Carrano. DATA ABSTRACTION AND PROBLEM SOLVING WITH C++