-
Notifications
You must be signed in to change notification settings - Fork 0
/
Maxheap.cpp
100 lines (94 loc) · 2.24 KB
/
Maxheap.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include "Maxheap.h"
using namespace std;
Maxheap::Maxheap(int k) : maxnumofscores(k), currnumofscores(0)
{
heap = (double *)malloc(maxnumofscores * sizeof(double));
ids = (int *)malloc(maxnumofscores * sizeof(int));
}
int Maxheap::minindex(int low, int high)
{
int min = -1;
double minscore = 1000000.0;
for (int i = low; i < high; i++)
{
if (heap[i] < minscore)
{
min = i;
minscore = heap[i];
}
}
return min;
}
void Maxheap::swapscores(int index1, int index2)
{
double temp = 0.0;
temp = heap[index1];
int tempid = ids[index1];
heap[index1] = heap[index2];
heap[index2] = temp;
ids[index1] = ids[index2];
ids[index2] = tempid;
}
void Maxheap::insert(double score, int id)
{
int index;
if (currnumofscores != maxnumofscores)
{
index = currnumofscores;
currnumofscores++;
}
else
{
int tempindex = minindex(maxnumofscores / 2, maxnumofscores);
if (score > heap[tempindex])
index = tempindex;
else
return;
}
heap[index] = score;
ids[index] = id;
while (heap[index] > heap[(index - 1) / 2])
{
swapscores(index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
int Maxheap::Maxchild(int number1, int number2)
{
if(number1<currnumofscores && number2<currnumofscores)
{
if(heap[number1>heap[number2]])
return number1;
else
return number2;
}
else if(number1<currnumofscores)
return number1;
else if(number2<currnumofscores)
return number2;
return -1;
}
double Maxheap::remove()
{
int index = 0, Chosenchild;
double Returnvalue = 0.0;
if (currnumofscores > 0)
{
Returnvalue = heap[0];
currnumofscores--;
heap[0] = heap[currnumofscores];
ids[0] = ids[currnumofscores];
while (1)
{
Chosenchild = Maxchild(2 * index + 1, 2 * index + 2);
if (Chosenchild != -1 && heap[Chosenchild] > heap[index])
{
swapscores(Chosenchild, index);
index = Chosenchild;
}
else
break;
}
}
return Returnvalue;
}