13,557,860 members
alternative version

#### Stats

63.3K views
24 bookmarked
Posted 7 Mar 2007
Licenced CPOL

# Heap Data Structure

, 7 Mar 2007
A C++ class that implements the data structure Heap.

## Introduction

This article briefly describes the notion of the Heap data structure and provides an implementation source code - the `CHeapTree` class. `CHeapTree` is an array based auto-resizing class that efficiently implements the Heap data structure.

## What is a Heap

The heap is a data structure which is a special kind of complete binary tree. The main distinction is that a Heap stores its nodes in a partial order. Also, the nodes are filled from left to right so that if a specific node has no left child, it should have no right child too. Also, if there is a node in level h, the level h - 1 should be fulfilled.

The following is a formal definition of the Heap [from Computer Algorithms by S. Baase and A. Van Gelder]:

A binary tree V is a Heap structure if and only if it satisfies the following conditions:

1. V is complete at least through depth h - 1
2. All leaves are at depth h or h - 1
3. All paths to a leaf of depth h are to the left of all paths to a leaf of depth h - 1

There are two kinds of Heaps - minheap and maxheap. A minheap is a Heap for which each node's priority is less than or equal to its children's priorities. A maxheap is a Heap for which each node's priority is greater than or equal to its children's priorities.

Examples of a maxheap (left) and a minheap (right):

## Basic Implementation Details

The class `CHeapTree` implements the Heap structure by an array in which the nodes are stored by reading the tree from top to down and from left to right. So, the above maxheap will be: 10, 9, 8, 6, 1, 5. In this representation, the children and the parent of the jth index can be identified as follows [assume zero based indexing]:

• Left_child_index = j * 2 - 1
• Right_child_index = j * 2 = Left_child_index + 1
• Parent_index = (j - 1) / 2

If any index is out of the array's boundaries, that node doesn't exist.

## The Cost

• The number of comparisons of keys done by the Heap construction: O(n)
• The number of comparisons of keys done by the Heap deletion: 2*n*lg(n)
• The number of comparisons of the Heap based sorting for both average and worst cases: BigTheta(n*lg(n) )

## CHeapTree declaration (details omitted)

```template <class TID, class TDATA>
class CHeapTree
{
struct _NODE {
TID id;
TDATA data;
};
_NODE *m_data;

public:
CHeapTree(int nInitMax = 100);
~CHeapTree();

bool IsEmpty() const { return m_nSize == 0; }
int GetSize() const { return m_nSize; }

void Insert(const TID &id, const TDATA &data);
bool RemoveTop();
bool RemoveAll();

bool GetTopID(TID *pid) const;
bool GetTopData(TDATA *pdata) const;
bool GetData(const TID &id, TDATA *pdata) const;

bool ResetData(const TID &id, const TDATA &data);

private:
void _ReformatHeap(int iRoot);
};```

The class implements the very basic operations of the heap. In `CHeapTree`, the data sorting takes place based on the `TDATA` type values. So, if your `TDATA` is a user-defined type, it should have the <, =, and > operators overloaded. The logic of comparison is up to the user. `TID` is a representative value such that each node can be uniquely identified by its `TID` value. If not, the sorting order is undefined.

By default, `CHeapTree` is a minheap. That is, `TDATA`'s lower values have greater priority. To make it a maxheap, you should change [converse] the logic of comparison operators for the `TDATA` type.

## How to Use

It's very simple to use this class. It might be something like this:

```// int=id, float=priority [as less as better]
CHeapTree<int, float> h;
h.Insert(0, 0.1f);
h.Insert(1, 0.2f);
h.Insert(2, 0.15f);
h.Insert(3, 0.3f);
h.Insert(4, 0.21f);

h.ResetData(3, 0.19f);
// The order should be [0, 2, 3, 1, 4]

while (!h.IsEmpty()) {
int top;
h.GetTopID(&top);
float data;
h.GetTopData(&data);
cout << "(" << top << " : " << data << ")\n";
h.RemoveTop();
}```

## The End

You can find the `CHeapTree` class attached to this page. If you have suggestions and notes, feel free to share them with me.

Happy programming!

## About the Author

 Software Developer 13 United States
No Biography provided

## You may also be interested in...

 Pro Pro

## Comments and Discussions

 First Prev Next
 STL has it, but this explains it jeffsheard23-Nov-07 5:58 jeffsheard 23-Nov-07 5:58
 stl already have bvsbvs7-Mar-07 9:34 bvsbvs 7-Mar-07 9:34
 Re: stl already have emilio_grv8-Mar-07 6:11 emilio_grv 8-Mar-07 6:11
 Re: stl already have bvsbvs8-Mar-07 8:47 bvsbvs 8-Mar-07 8:47
 Re: stl already have Arman Z. Sahakyan8-Mar-07 22:59 Arman Z. Sahakyan 8-Mar-07 22:59
 Re: stl already have kesselhaus21-Mar-07 15:56 kesselhaus 21-Mar-07 15:56
 Re: stl already have Wong Shao Voon8-Mar-07 22:39 Wong Shao Voon 8-Mar-07 22:39
 Last Visit: 31-Dec-99 18:00     Last Update: 25-May-18 14:41 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.