---

Heap.cc

Go to the documentation of this file.

/*
    File:       Heap.cc

    Function:   

    Author:     Andrew Willmott

    Notes:      
*/

#include "cl/Heap.h"


HeapEntry *Heap::RemoveMax()
{
    HeapEntry   *result;

    if (heap.NumItems() == 0)
        return(0);
        
    result = heap[0];
    result->heapIdx = -1;

    heap[0] = heap.Last();
    heap[0]->heapIdx = 0;
    heap.Shrink(1);

    HeapifyDown(0);

    return(result);
}

Void Heap::Insert(HeapEntry *he)
{   
    heap.Append(he);
    he->heapIdx = heap.NumItems() - 1;

    HeapifyUp(heap.NumItems() - 1);
}
    
Void Heap::Delete(HeapEntry *he)
{   
    Assert(he->heapIdx >= 0, "Heap entry already deleted");

    if (he->heapIdx < 0)
        return;
        
    heap[he->heapIdx] = heap.Last();
    heap[he->heapIdx]->heapIdx = he->heapIdx;
    heap.Shrink(1);
    
    HeapifyDown(he->heapIdx);

    he->heapIdx = -1;
}
    
Void Heap::Update(HeapEntry *he)
{   
    Int     i = he->heapIdx;
    
    Assert(i >= 0, "Can't update deleted entry");

    if (i > 0 && heap[Parent(i)]->cost < he->cost)
        HeapifyUp(i);
    else
        HeapifyDown(i);
}
    
Void Heap::HeapifyDown(Int i)
{
    Int     child, parent;

    parent = i;
    child = Left(i);

    while (child < heap.NumItems())
    {
        if (child + 1 < heap.NumItems() && heap[child]->cost < heap[child + 1]->cost)
            child++;

        if (heap[child]->cost > heap[parent]->cost)
        {
            Swap(heap[child]->heapIdx, heap[parent]->heapIdx);
            Swap(heap[child], heap[parent]);

            parent = child;
            child = Left(parent);
        }
        else
            break;
    }
}

Void Heap::HeapifyUp(Int i)
{
    Int     child, parent;
    
    child = i;
    parent = Parent(child);

    while (parent >= 0)
    {
        if (heap[parent]->cost < heap[child]->cost)
        {
            Swap(heap[child]->heapIdx, heap[parent]->heapIdx);
            Swap(heap[child], heap[parent]);
            child = parent;
            parent = Parent(child);
        }
        else
            break;
    }
}

---