Homework SourseMax heap priority queue using C Cannot use vector or stack
Max heap priority queue using C++
Cannot use vector or stack & queue stl libraries
I need a max heap priority queue that takes an id number and a priority number and impelemnts them into an array. And would out put the numbers based on priority. Output should display the priority number first followed by the id number. Ex: 3-135, 13-292, etc.
it is to read in 100 request, print out the first 20 (like the output listed above), and delete 50 request. That is the first output.
The second output will, read in 100 more requests, print out the first 30 , and delete 50 requests.
The third and final output will read in the read of the file and print out 40 request and delete them.
Here is the data;
167-21
200-14
224-24
258-13
164-17
245-15
127-11
191-11
242-20
136-22
104-16
253-12
282-17
216-16
195-18
226-12
238-21
212-19
199-12
194-20
111-18
233-12
164-13
211-16
168-18
144-12
257-17
159-22
241-18
278-14
135-11
142-15
206-13
242-20
148-14
105-21
229-15
250-20
201-16
248-13
123-19
254-19
140-16
276-11
208-21
139-19
223-21
238-12
182-18
241-19
215-13
158-14
230-19
206-22
286-18
245-21
172-24
129-10
273-12
212-22
190-11
136-21
267-15
274-10
152-21
250-15
224-16
130-11
291-22
237-17
187-17
283-13
209-15
258-14
288-21
246-12
130-21
268-13
291-10
155-22
259-20
237-19
183-18
141-20
250-12
136-11
120-24
121-16
299-13
184-13
234-11
299-18
238-13
288-10
167-17
193-18
183-13
121-12
117-10
214-23
116-24
151-15
149-15
256-14
203-23
108-24
109-19
202-14
185-10
243-13
287-23
203-14
100-18
118-13
296-10
181-18
298-24
257-14
122-22
192-23
279-18
157-20
291-18
188-10
211-11
134-12
155-12
146-13
186-17
133-15
242-14
116-19
298-21
151-12
199-11
176-12
289-17
212-15
210-15
169-13
188-21
289-16
123-10
285-17
185-12
126-23
257-22
232-17
254-24
289-21
229-21
192-23
255-15
249-24
212-11
160-20
253-23
123-24
296-14
229-17
137-14
249-16
295-23
116-22
205-21
182-18
234-15
201-19
171-21
163-21
255-18
153-10
108-22
245-12
256-18
258-11
282-16
244-11
122-16
261-14
150-10
166-23
159-24
139-22
124-13
210-19
149-15
213-11
122-14
118-18
205-17
291-13
125-12
114-12
124-24
174-19
259-22
170-23
197-12
277-13
170-23
168-18
285-12
180-22
127-18
199-12
125-12
224-23
272-23
281-21
132-23
293-10
131-10
242-12
186-12
200-24
260-12
274-13
270-15
133-20
260-11
167-21
250-20
194-15
124-20
225-24
194-21
202-18
166-11
293-23
184-11
164-23
252-24
187-20
226-20
257-20
215-20
127-16
258-23
209-19
186-17
187-10
174-22
127-10
228-14
220-23
262-12
296-13
161-12
225-20
160-14
216-17
226-15
271-11
247-16
220-13
224-10
263-18
151-15
129-12
213-10
278-23
107-20
100-12
139-13
260-18
224-17
208-22
187-18
150-11
128-10
284-13
240-20
204-11
256-20
250-22
185-23
116-16
257-16
257-16
171-22
261-14
122-21
212-17
196-22
141-15
229-13
265-14
232-14
155-16
262-18
234-24
272-19
269-17
263-12
183-22
135-21
148-12
238-20
242-13
Solution
#include<iostream>
using namespace std;
const int MAX=100;
struct data
{
int val,p; /* val stores the value and p stores the respective priority*/
}d[MAX];
int heapsize=0,length=0;
data temp;
int parent(int i) {
return (i/2);
}
int left(int i) {
return 2*i;
}
int right(int i) {
return (2*i+1);
}
void minheapify(data a[],int i) /* min heapify(min value at first) using the key of the data */
{
int l=left(i);
int smallest;
int r=right(i);
if (l<=heapsize && a[l].p<a[i].p)
smallest=l;
else smallest=i;
if (r<=heapsize && a[r].p<a[smallest].p)
smallest=r;
if (!(smallest==i))
{
temp=a[i];
a[i]=a[smallest];
a[smallest]=temp;
minheapify(a,smallest);
}
}
int heap_min(data a[]) {
return a[1].p;
}
int buildminheap(data a[],int length) {
heapsize=length;
for(int l=(length/2);l>1;l--)
minheapify(a,l);
}
void heapincp(data a[],int i,int ps) {
if (ps>a[i].p)
cout<<\"ERROR\";
a[i].p=ps;
while((i>1) && (a[parent(i)].p>a[i].p))
{
temp=a[i];
a[i]=a[parent(i)];
a[parent(i)]=temp;
i=parent(i);
}
}
int heap_extract_min(data a[]) {
if (heapsize<1)
cout<<\"ERROR UNDERFLOW\";
int minimum = a[1].val;
a[1]= a[heapsize];
heapsize--;
minheapify(a,1);
return minimum;
}
void min_heap_insert(data a[],int p)
{
heapsize+=1;
a[heapsize].p = 100000000;
heapincp(a,heapsize,p);
}
int main()
{
char op;
do
{
int ch;
cout<<\"----------Menu-------------\ \ \";
cout<<\"\\t1.Insertion\ \\t2.Extract\";
cout<<\"\ \ \\tEnter your Choice<1,2> ?\";
cin>>ch;
switch(ch)
{
case 1 : length++;
cout<<\"Enter Value ?\";
cin>>d[length].val;
cout<<\"Enter Priority (KEY) ?\";
cin>>d[length].p;
min_heap_insert(d,d[length].p);
break;
case 2 : cout<<\"\ PRIORITY QUEUE\ \";
cout<< heap_extract_min(d)<<\"\\t\";
length--;
break;
}
cout<<\"\ \ Do You Want to Continue <Y/N> ?\";
cin>>op;
} while(op==\'Y\' || op==\'y\');
return 0;
}
