---

Heap.h

Go to the documentation of this file.

/*
    File:       Heap.h

    Function:   Implements a simple binary heap. From Manber's
                "Introduction to Algorithms."

    Author:     Andrew Willmott

    Copyright:  (c) 2000, Andrew Willmott
*/

#ifndef __Heap__
#define __Heap__

#include "cl/PtrArray.h"

struct HeapEntry
{
    Float   cost;   
    Int     heapIdx;
};

typedef PtrArray<HeapEntry> HeapEntries;

class Heap
{
public:

// operations needed for a priority queue

    Void        Insert(HeapEntry *he);
    // add he to the heap.
    Void        Delete(HeapEntry *he);
    // remove he from the heap.
    Void        Update(HeapEntry *he);
    // signal that he's cost has been updated
    HeapEntry   *RemoveMax();
    // remove highest cost node.

    Int         NumItems()
                { return(heap.NumItems()); };

    Void        HeapifyUp(Int i);
    Void        HeapifyDown(Int i);

    Int         Parent(Int i)
                { return((i - 1) / 2); }
    Int         Left(Int i)
                { return(2 * i + 1); }
    Int         Right(Int i)
                { return(2 * i + 2); }

    HeapEntries heap;
};

#endif

---