Heap Data Structure

• Download source - 1.23 Kb

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 j^th 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!