maxHeap Class Reference

#include <heap.h>

Public Member Functions
	maxHeap (int size)
	~maxHeap ()
int	numElements ()
int	insert (InfoRecord *)
InfoRecord *	deleteMax ()
InfoRecord *	iterator (heapIterator *)
InfoRecord *	next (heapIterator *)

Detailed Description

Definition at line 43 of file heap.h.

Constructor & Destructor Documentation

maxHeap()

maxHeap::maxHeap

(

int

size

)

Definition at line 110 of file heap.C.

{
  this->size = size;
  h = new heapRecord[size];
  count = 0;
}

~maxHeap()

maxHeap::~maxHeap

(

)

Definition at line 117 of file heap.C.

                  {
  delete [] h;
}

Member Function Documentation

deleteMax()

InfoRecord * maxHeap::deleteMax

(

)

Definition at line 152 of file heap.C.

References msm::swap().

Referenced by RefineTorusLB::newRefine(), and Rebalancer::refine().

{
  if (count == 0) return 0;
  InfoRecord *tmp = h[0].info;
  int best;

  h[0] = h[count-1];
  count--;

  int current = 0;
  int c1 = 1;
  int c2 = 2;
  while (c1 < count)
    {
      if (c2 >= count)
        best = c1;
      else
        {
          if (h[c1].info->load > h[c2].info->load)
            best = c1;
          else
            best = c2;
        }
      if (h[best].info->load > h[current].info->load)
        {
          swap(best, current);
          current = best;
          c1 = 2*current + 1;
          c2 = c1 + 1;
        }
      else
        break;
    }
  return tmp;
}

insert()

int maxHeap::insert

(

InfoRecord *

x

)

Definition at line 126 of file heap.C.

References msm::swap().

Referenced by Rebalancer::makeHeaps(), Rebalancer::makeTwoHeaps(), RefineTorusLB::newRefine(), and Rebalancer::refine().

{
  h[count].info = x;
  h[count].deleted  = 0;
  int current = count;
  count++;

  if (count >= size) {
    std::cout << "maxHeap overflow. \n" ; 
    return -1;}

  int parent = (current - 1)/2;
  while (current != 0)
    {
      if (h[current].info->load > h[parent].info->load)
        {
          swap(current, parent);
          current = parent;
          parent = (current-1)/2;
        }
      else
        break;
    }
  return 0;
}

iterator()

InfoRecord * maxHeap::iterator

(

heapIterator *

iter

)

Definition at line 189 of file heap.C.

References heapIterator::next.

                                               {
  iter->next = 1;
  if (count == 0)
    return 0;
  return h[0].info;
}

next()

InfoRecord * maxHeap::next

(

heapIterator *

iter

)

Definition at line 196 of file heap.C.

References heapIterator::next.

                                           {
  if (iter->next >= count)
    return 0;
  iter->next += 1;
  return h[iter->next - 1].info;
}

numElements()

int maxHeap::numElements

(

)

Definition at line 121 of file heap.C.

{
  return count;
}

---

The documentation for this class was generated from the following files:

• heap.h
• heap.C