C++

Forum

 
how to make a priority queue/min heap

andrewthecoder (26)
im working on a program and what i have to do is pass in process time of jobs into a priority queue processing min time jobs first. there is also a high priority job which should stop everything and be processed right away which is the 30 with priority 1 job. im stuck on how to do this i have my jobs being created and their processing times done. i am trying to make a function where i would pass thoe processing times in along with priority to put them into the queue to be processed but i have no idea how to implement this. this is my code so far creating all the jobs and process times. ive never used priority queues or heaps and i tried googling it to learn but i just dont understand if any1 can exaplin what to do or how i can achieve this that would be great.

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
 
void createjobs(int start)
{

	int randnum=0;
	int endtime = 200;
	srand(time(0));
	for (int time = 1; 0 < endtime; time++)
	{
		int temp1 = 4, temp2 = 9, temp3 = 24, temp4 = 25;
		if (time % 5 == 0 && time % 10 == 0 && time % 25 == 0 && time % 30==0)
		{
			cout << "job 4 time " << time << endl;
			addjobtime5(time);
			randnum = rand() % (3);
			temp1 = temp1 + randnum;
			endtime = endtime - temp1;
			cout << "job 5 temp1: " << temp1 << "  randy " << randnum << "end " << endtime << endl;
			addjobtime10(time);
			randnum = rand() % (3);
			temp2 = temp2 + randnum;
			endtime = endtime - temp2;
			cout << "job 10 temp 2: " << temp2 << "  randy " << randnum << "end " << endtime << endl;
			addjobtime25(time);
			randnum = rand() % (3);
			temp3 = temp3 + randnum;
			endtime = endtime - temp3;
			cout << "job 25 " << temp3 << "  randy " << randnum << "end " << endtime << endl;
			addjobtime30(time);
			randnum = rand() % (11);
			temp4 = temp4 + randnum;
			endtime = endtime - temp4;
			cout << "job 30 " << temp4 << "  randy " << randnum << "end " << endtime << endl;
		}
		else if (time % 5 == 0 && time % 10 == 0 && time % 30 == 0)
		{
			cout << "job 6 time " << time << endl;
			addjobtime5(time);
			randnum = rand() % (3);
			temp1 = temp1 + randnum;
			endtime = endtime - temp1;
			cout << "job 5  temp1: " << temp1 << "  randy " << randnum << "end " << endtime << endl;
			addjobtime10(time);
			randnum = rand() % (3);
			temp2 = temp2 + randnum;
			endtime = endtime - temp2;
			cout << "job 10 temp2: " << temp2 << "  randy " << randnum << "end " << endtime << endl;
			addjobtime30(time);
			randnum = rand() % (11);
			temp4 = temp4 + randnum;
			endtime = endtime - temp4;
			cout << "job 30 " << temp4 << "  randy " << randnum << "end " << endtime << endl;
		}
		else if (time % 5 == 0 && time % 25 == 0 && time % 30==0)
		{
			cout << "job 7 time " << time << endl;
			addjobtime5(time);
			randnum = rand() % (3);
			temp1 = temp1 + randnum;
			endtime = endtime - temp1;
			cout << "job 5 temp1: " << temp1 << "  randy " << randnum << "end " << endtime << endl;
			addjobtime25(time);
			randnum = rand() % (3);
			temp3 = temp3 + randnum;
			endtime = endtime - temp3;
			cout << "job 25 " << temp3 << "  randy " << randnum << "end " << endtime << endl;
			addjobtime30(time);
			randnum = rand() % (11);
			temp4 = temp4 + randnum;
			endtime = endtime - temp4;
			cout << "job 30 " << temp4 << "  randy " << randnum << "end " << endtime << endl;
		}
		else if (time % 5 == 0 && time % 30==0)
		{
			cout << "job 8 time " << time << endl;
			addjobtime5(time);
			randnum = rand() % (3);
			temp1 = temp1 + randnum;
			endtime = endtime - temp1;
			cout << "job 5 temp 1: " << temp1 << "  randy " << randnum << "end " << endtime << endl;
			addjobtime30(time);
			randnum = rand() % (11);
			temp4 = temp4 + randnum;
			endtime = endtime - temp4;
			cout << "job 30 " << temp4 << "  randy " << randnum << "end " << endtime << endl;
		}
		else if (time % 5 == 0 && time % 25==0)
		{
			cout << "job 12 time " << time << endl;
			addjobtime5(time);
			randnum = rand() % (3);
			temp1 = temp1 + randnum;
			endtime = endtime - temp1;
			cout << "job 5 temp1: " << temp1 << "  randy " << randnum << "end " << endtime << endl;
			addjobtime25(time);
			randnum = rand() % (3);
			temp3 = temp3 + randnum;
			endtime = endtime - temp3;
			cout << "job 25 " << temp3 << "  randy " << randnum << "end " << endtime << endl;
		}

		else if (time % 5 == 0 && time % 10==0)
		{
			cout << "job 13 time " << time << endl;
			addjobtime5(time);
			randnum = rand() % (3);
			temp1 = temp1 + randnum;
			endtime = endtime - temp1;
			cout << "job 5 temp1:  " << temp1 << "  randy " << randnum << "end " << endtime << endl;
			addjobtime10(time);
			randnum = rand() % (3);
			temp2 = temp2 + randnum;
			endtime = endtime - temp2;
			cout << "job 10 temp2: " << temp2 << "  randy " << randnum << "end " << endtime << endl;
		}
		else if (time % 10 == 0 && time % 30==0)
		{
			cout << "job 9 time " << time << endl;
			addjobtime10(time);
			randnum = rand() % (3);
			temp2 = temp2 + randnum;
			endtime = endtime - temp2;
			cout << "job 10 temp 2: " << temp2 << "  randy " << randnum << "end " << endtime << endl;
			addjobtime30(time);
			randnum = rand() % (11);
			temp4 = temp4 + randnum;
			endtime = endtime - temp4;
			cout << "job 30 " << temp4 << "  randy " << randnum << "end " << endtime << endl;
		}
		else if (time % 10 == 0)
		{
			cout << "job 16 time " << time << endl;
			addjobtime10(time);
			randnum = rand() % (3);
			temp2 = temp2 + randnum;
			endtime = endtime - temp2;
			cout << "job 10 temp2 : " << temp2 << "  randy " << randnum << "end " << endtime << endl;
		}
		else if (time % 25 == 0)
		{
			cout << "job 11 time " << time << endl;
			addjobtime25(time);
			randnum = rand() % (3);
			temp3 = temp3 + randnum;
			endtime = endtime - temp3;
			cout << "job 25 " << temp3 << "  randy " << randnum << "end " << endtime << endl;
		}
		else if (time % 5 == 0)
		{
			cout << "job 18 time " << time << endl;
			addjobtime5(time);
			randnum = rand() % (3);
			temp1 = temp1 + randnum;
			endtime = endtime - temp1;
			cout << "job 5 temp1: " << temp1 << "  randy " << randnum << "end " << endtime << endl;
		}
		else if (time % 30 == 0)
		{
			cout << "job 122 time " << time << endl;
			addjobtime30(time);
			randnum = rand() % (11);
			temp4 = temp4 + randnum;
			endtime = endtime - temp4;
			cout << "job 30 " << temp4 << "  randy " << randnum << "end " << endtime << endl;
		}
		else
		{
			cout << "shit" << endl;
		
		}
	}
}

void addjobtime5(int time)
{
	int process5time = 1;
	int randnum = rand() % (6);
	process5time = process5time + randnum;
	pass2queue(process5time, 2);
	cout << "processing time for job 1: " << process5time << "= 1 + " << randnum << endl;
	//cout << "job 5 time YO ITS DIVISIBLE BY 5->" << time << endl;
}

void addjobtime10(int time)
{
	int process10time = 6;
	int randnum = rand() % (6);
	process10time = process10time + randnum;
	pass2queue(process10time, 2);
	cout << "processing time for job 2: " << process10time << "= 6 + " << randnum << endl;
	//cout << "job 10 time YO ITS DIVISIBLE BY 10 -> " << time << endl;
}

void addjobtime25(int time)
{
	int process25time = 11;
	int randnum = rand() % (6);
	process25time = process25time + randnum;
	pass2queue(process25time, 2);
	cout << "processing time for job 3: " << process25time << "= 11 + " << randnum << endl;
	//cout << "job 25 time YO ITS DIVISIBLE BY 25->" << time << endl;
}
void addjobtime30(int time)
{
	int process30time = 8;
	int randnum = rand() % (6);
	process30time = process30time + randnum;
	pass2queue(process30time, 1);
	cout << "processing time for job 4:  " << process30time << "= 8 + " << randnum << endl;
	//cout << "job 30 time YO ITS DIVISIBLE BY 30->" << time << endl;
}

void pass2queue(int processtime, int priority)
{

}
dhayden (5795)
priority_queue is part of the STL. Just use that.
http://www.cplusplus.com/reference/queue/priority_queue/
andrewthecoder (26)
@dhayden
i was trying to do that but it didnt work with me i was just trying to store it in a regular queue and that wasnt really working when im trying to print it out

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
 
void pass2queue(int processtime, int priority, int endtime)
{
	int holder = endtime;
	int protime = processtime;
	cout << " THE DAM FUCKIN END TIME " << holder << " pro time " << protime << endl;
	queue<int>myqueue;
	if (holder >= 0)
	{
		cout << "stored " << protime << " in queue " << endl;
		myqueue.push(protime);
	}
	else if (holder < 0)
	{
		printqueue(myqueue);
	}
}

void printqueue(queue<int> myqueue)
{
	cout << " WE OUTH ERE " << endl;
	queue<int>holderq = myqueue;
	cout << myqueue.front() << "   fsf " << endl;
	while (!holderq.empty())
	{
		cout << holderq.front() << " top of queue" << endl;
		holderq.pop();
	}
}
dhayden (5795)
In your example, myqueue is a local variable and you are either adding something to it (lines 9-10) or printing it out (line 14) but not both, so you're guaranteed to print an empty queue only.

Your priority queue must be part of the class or passed into pass2queue by reference etc. Also, what's in the priority queue probably has to be a class containing the process priority, remaining process runtime, maybe process id. You might call it class Process :). Add an operator <() to sort the Jobs by priority.
danghotties (34)
As dhayden suggested, you can modify the STL priority queue. You can declare a modified priority queue like:
priority_queue<Job, vector<Job>, "Some comparative here"> myQueue;
This means that the priority queue is filled with a class Job, which can have your different times and priority in it; it uses a vector for queue storage, and the last one is the comparing method on how to sort things within the queue.
You can make your own operator overload class function to tell the queue how you want things sorted. Since you said by processing times, you can make a class function that overloads () and takes in two types of jobs, compares their processing time, and return true/false if one job is lower processing time than the other.

Check out this website: http://comsci.liu.edu/~jrodriguez/cs631sp08/c++priorityqueue.html
About half way down the page is what I'm talking about.
Last edited on
andrewthecoder (26)
@dhayden
ok so i think my first problem is i dont have a class. never learned them too well so i need a class to make the priority queue to work?
andrewthecoder (26)
what i was trying to do it while the endtime is greater than 0 add the stuff to the queue then when the endtime goes below 0 it would print it all out
andrewthecoder (26)
@danghotties
so like when you delcare all those things inside the priority queue and class it will automatically run those each time some thing is put into it automatically storing it??
danghotties (34)
Yes, any time you push/pop to/from queue it will adjust itself based on the specifications you made when declared.
andrewthecoder (26)
@danghotties
Ok now it's starting to make more sense ima go try it see what I can do :)
Topic archived. No new replies allowed.