Click here to Skip to main content
11,710,943 members (84,393 online)
Click here to Skip to main content

Heap Data Structure

, 7 Mar 2007 CPOL 51.4K 644 24
Rate this:
Please Sign up or sign in to vote.
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):

Maxheap exampleMinheap example

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!

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Arman S.
Software Developer 13
United States United States
No Biography provided

You may also be interested in...

Comments and Discussions

 
GeneralSTL has it, but this explains it Pin
jeffsheard23-Nov-07 5:58
memberjeffsheard23-Nov-07 5:58 
Generalstl already have Pin
bvsbvs7-Mar-07 9:34
memberbvsbvs7-Mar-07 9:34 
GeneralRe: stl already have Pin
emilio_grv8-Mar-07 6:11
memberemilio_grv8-Mar-07 6:11 
GeneralRe: stl already have Pin
bvsbvs8-Mar-07 8:47
memberbvsbvs8-Mar-07 8:47 
GeneralRe: stl already have Pin
Arman Z. Sahakyan8-Mar-07 22:59
memberArman Z. Sahakyan8-Mar-07 22:59 
GeneralRe: stl already have Pin
kesselhaus21-Mar-07 15:56
memberkesselhaus21-Mar-07 15:56 
GeneralRe: stl already have Pin
Wong Shao Voon8-Mar-07 22:39
memberWong Shao Voon8-Mar-07 22:39 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150819.1 | Last Updated 7 Mar 2007
Article Copyright 2007 by Arman S.
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid