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
101
102
103
104
105
106
|
void push(T value){
if(stuff.size() == 0){
stuff.push_back(value);
last_value= stuff[stuff.size()-1];
heap_size++;
return;
}
else if(stuff.size() != 0){
stuff.resize(stuff.size() + 1, value);
heap_size++;
last_value = stuff[stuff.size()-1];
}
int s = 0;
int parent_index= (s-1)/2;
while(s < stuff.size()){//here we iterate through the list, and check to make sure the parent is less than the child.
if(stuff[s] < stuff[parent_index]){
swap(stuff[s], stuff[parent_index]);
s=0;
}
s++;
parent_index= (s-1)/2;
}
return;
}
void pop(){
//first inside delete we check to see if the size is zero, if so, return
if(stuff.size() == 0)
return;
else if(stuff.size() == 1 || stuff.size() == 2){//if the size of the vector is equal to one or two
sorted_stuff.push_back(stuff[0]);//push the root into the sorted stuff vector
stuff.erase(stuff.begin());//erase the first element of the vector
heap_size--;//decrement heap_size
return;//return
}
else if(stuff.size() == 3){//if size of the vector is equal to 3
sorted_stuff.push_back(stuff[0]);//push back the root into the sorted stuff vector
stuff.erase(stuff.begin());//erase the root element
if(stuff[0] > stuff[1])//check to see which child is bigger, see if the child in location 0 is largest value
swap(stuff[0], stuff[1]);//...if so, swap with the smaller value, which will now be the root
heap_size--;//decrenent heap_size
return;
}
else{
//if size is greater than 3
sorted_stuff.push_back(stuff[0]);//push the root into the sorted stuff vector
//cout<<"stuff [size-1]1: " << stuff[stuff.size()-1] << endl;
stuff[0] = stuff[stuff.size()-1];//change the element at the root to the last inserted value , list-size (-) 1
//cout<<"stuff [0]: " << stuff[0] << endl;
stuff.pop_back();//pop out the last element of the vector
//cout<<"stuff [size-1]2: " << stuff[stuff.size()-1] << endl;
heap_size--;//decrement heap_size
//now we check to see which value is the smaller between the two children & store the minimum value
int s = 0;
int l_i = (s * 2) + 1;//index for the left child
int r_i = (s * 2) + 2;//index for the right child
int min_child = 0;//indec for the smallest child
//compare the two children to know which one to swap into the root after deletion
if(stuff[l_i] < stuff[r_i])
min_child= l_i;
else min_child = r_i;
int parent_index = (s-1)/2;//calculate the index of the parent node
while(s < stuff.size() && l_i < stuff.size() && r_i < stuff.size()){
//cout<<"st[pi]: "<<stuff[parent_index]<< ", st[mc]: " << stuff[min_child]<< endl;
if(stuff[min_child] < stuff[parent_index]){
//cout<<"st[pi]: "<<stuff[parent_index]<< ", st[mc]: " << stuff[min_child]<< endl;
swap(stuff[min_child], stuff[parent_index]);
s = 0;
//cout<<"postswap\nst[pi]: "<<stuff[parent_index]<< ", st[mc]: " << stuff[min_child]<< endl;
}
s++;
parent_index = (s-1)/2;//update the parent index
l_i = (s * 2) + 1;//update the left child index
r_i = (s * 2) + 2;//update the right child index
//updates min child
if(l_i < stuff.size() && r_i < stuff.size()){//if the
if(stuff[l_i] < stuff[r_i])
min_child= l_i;
else min_child = r_i;
}
else if(l_i == stuff.size() || r_i == stuff.size()){
if(l_i == stuff.size())
min_child= l_i;
else if (r_i == stuff.size()){
if(stuff[l_i] < stuff[r_i])
min_child = l_i;
else min_child = r_i;
}
//cout<<"stuff last: " <<stuff[min_child] << endl;
if(stuff[min_child] < stuff[parent_index]){
//cout<<"st[pi]: "<<stuff[parent_index]<< ", st[mc]: " << stuff[min_child]<< endl;
swap(stuff[min_child], stuff[parent_index]);
s = 0;
}
//else break;
}
}
}
}
|
