minHeap Class Reference

#include <heap.h>

Public Member Functions
	minHeap (int size)
	~minHeap ()
int	numElements ()
int	insert (InfoRecord *)
InfoRecord *	deleteMin ()
InfoRecord *	iterator (heapIterator *)
InfoRecord *	next (heapIterator *)

Detailed Description

Definition at line 20 of file heap.h.

Constructor & Destructor Documentation

minHeap()

minHeap::minHeap

(

int

size

)

Definition at line 14 of file heap.C.

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

~minHeap()

minHeap::~minHeap

(

)

Definition at line 21 of file heap.C.

                  {
  delete [] h;
}

Member Function Documentation

deleteMin()

InfoRecord * minHeap::deleteMin

(

)

Definition at line 57 of file heap.C.

References msm::swap().

{
  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 minHeap::insert

(

InfoRecord *

x

)

Definition at line 30 of file heap.C.

References msm::swap().

Referenced by Rebalancer::makeHeaps(), and Rebalancer::makeTwoHeaps().

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

  int current = count;
  count++;

  if (count >= size) {
    std::cout << "minHeap 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 * minHeap::iterator

(

heapIterator *

iter

)

Definition at line 94 of file heap.C.

References heapIterator::next.

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

next()

InfoRecord * minHeap::next

(

heapIterator *

iter

)

Definition at line 100 of file heap.C.

References heapIterator::next.

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

numElements()

int minHeap::numElements

(

)

Definition at line 25 of file heap.C.

{
  return count;
}

---

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

• heap.h
• heap.C