Free Web Site - Free Web Space and Site Hosting - Web Hosting - Internet Store and Ecommerce Solution Provider - High Speed Internet

Heap data structure

VB Articles

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 sub-trees.

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²).

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 semi-heap.
Trickle 7 down to correct position by turning the semi-heap 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++