NAMD
Public Member Functions | List of all members
minHeap Class Reference

#include <heap.h>

Public Member Functions

 minHeap (int size)
 
 ~minHeap ()
 
int numElements ()
 
int insert (InfoRecord *)
 
InfoRecorddeleteMin ()
 
InfoRecorditerator (heapIterator *)
 
InfoRecordnext (heapIterator *)
 

Detailed Description

Definition at line 20 of file heap.h.

Constructor & Destructor Documentation

minHeap::minHeap ( int  size)

Definition at line 14 of file heap.C.

15 {
16  this->size = size;
17  h = new heapRecord[size];
18  count = 0;
19 }
Definition: heap.h:9
minHeap::~minHeap ( )

Definition at line 21 of file heap.C.

21  {
22  delete [] h;
23 }

Member Function Documentation

InfoRecord * minHeap::deleteMin ( )

Definition at line 57 of file heap.C.

References msm::swap().

58 {
59  if (count == 0) return 0;
60 
61  InfoRecord *tmp = h[0].info;
62  int best;
63 
64  h[0] = h[count-1];
65  count--;
66 
67  int current = 0;
68  int c1 = 1;
69  int c2 = 2;
70  while (c1 < count)
71  {
72  if (c2 >= count)
73  best = c1;
74  else
75  {
76  if (h[c1].info->load < h[c2].info->load)
77  best = c1;
78  else
79  best = c2;
80  }
81  if (h[best].info->load < h[current].info->load)
82  {
83  swap(best, current);
84  current = best;
85  c1 = 2*current + 1;
86  c2 = c1 + 1;
87  }
88  else
89  break;
90  }
91  return tmp;
92 }
InfoRecord * info
Definition: heap.h:12
int minHeap::insert ( InfoRecord x)

Definition at line 30 of file heap.C.

References msm::swap(), and x.

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

31 {
32  h[count].info = x;
33  h[count].deleted = 0;
34 
35  int current = count;
36  count++;
37 
38  if (count >= size) {
39  std::cout << "minHeap overflow. \n" ;
40  return -1;}
41 
42  int parent = (current - 1)/2;
43  while (current != 0)
44  {
45  if (h[current].info->load < h[parent].info->load)
46  {
47  swap(current, parent);
48  current = parent;
49  parent = (current-1)/2;
50  }
51  else
52  break;
53  }
54  return 0;
55 }
short deleted
Definition: heap.h:11
gridSize x
InfoRecord * info
Definition: heap.h:12
InfoRecord * minHeap::iterator ( heapIterator iter)

Definition at line 94 of file heap.C.

References heapIterator::next.

94  {
95  iter->next = 1;
96  if (count == 0)
97  return 0;
98  return h[0].info;
99 }
int next
Definition: heap.h:17
InfoRecord * info
Definition: heap.h:12
InfoRecord * minHeap::next ( heapIterator iter)

Definition at line 100 of file heap.C.

References heapIterator::next.

100  {
101  if (iter->next >= count)
102  return 0;
103  iter->next += 1;
104  return h[iter->next - 1].info;
105 }
int next
Definition: heap.h:17
InfoRecord * info
Definition: heap.h:12
int minHeap::numElements ( )

Definition at line 25 of file heap.C.

26 {
27  return count;
28 }

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