so i am basically doing an assignment priority queue using heap
these are instructions for every commands
1 - add element create an element with the id an priority given
add the element to the queue
produce no output for this command
2 - delete element deleted the element with specified id from the queue
produce no output for this command
3 - reset priority locate the element with the specified id within the priority queue
change the element’s priority to the value requested
produce no output for this command
4 - read query the highest priority element from the queue
print the current (overall total) command number, the element id and priority on
standard output, followed by a newline, as follows:
i.e.: at command number 5087, top of queue is element 99 with priority 1
do not print the "read command number" at this time
5 - pop query the highest priority element and remove it from the queue
produce no output for this command
6 - finalize successively read and pop all elements remaining in the queue
provide output consistent with the read command for each remaining element
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
|
#include <iostream>
#include <array>
#include <algorithm>
using namespace std;
Private:{
heapElement heap[1000];
int heapSize=0;
}
struct elment_priority {
int element;
int priority;
};
void addElement(heapElement,int newThing, int heapSize){
heap[heapSize]= newThing;
heapSize++;
heapifyUp(int insert);
}
void heapifyUp(int insert){
int parent = ()(insert+1)/2)-1;
while(heap[insert].priority < heap[parent].priority){
swap(heap[insert], heap[parent]);
insert=parent;
parent= max(((insert+1)/2)-1,0);
}
}
void pop(int heapSize){
heap[0]=heap[heapSize-1]; //overwrite
heapSize--;
heapifyDown(0);
}
void heapifyDown(int insert){
int nextStep = insert;
right = (insert + 1)*2;
left=right-1;
if (left<heapSize){
nextStep=left;
}
if((right<heapSize)&&(heap[right].priority<heap[left].priority)){
nextStep=right;
}
while(heap[nextStep].priority < heap[insert].priority){
swap(heap[nextStep, heap[insert]]);
insert=nextStep;
}
right=()insert+1)*2;
leaft=right-1;
if(left<heapSize){
nextStep=left;
}
if((right<heapSize)&&heap[right].priority<heap[left].priority){
nextStep=right;
}
}
void deleteElement(heapElement, int element, int heapSize){
int index; // to remember the deleted node's position
for(int i=1; i <heapSize; i++){
if (heap[i] == element){
heap[i]=NULL;
index = i; // position of removed element;
break;
}
}
// move the last element(A[num_items_in_array]) in array to the position of removed element; heapify up/down according to priority
}
void reset(int element, int newP){
for(int i=1; i <heapSize; i++){
if (heap[i] == element){
heap[i].priority = newP;
heapifyDown(heap[i], newP);
heapifyUp(heap[i], newP);
}
}
}
void read(){
if(!heap[].empty()){
cout << heap[0];
}
}
void finalize(){
for(i=1; i<heapSize; i++){
cout << heap[i];
heap[i]=NULL;
}
}
int main()
{
int case, counter;
elment_priority node;
while(counter < 1000){
cin >> case;
cin >> node.element;
cin >> node.priority;
int addSum, deleteSum, resetSum, readSum, popSum, finalizeSum, totalSum=0;
switch(case) {
case 1:
addElement(heapElement,node.element, heapSize);
addSum++;
case 2:
deleteElement(heapElement,node.element, heapSize);
deleteSum++:
case 3:
reset(node.element, node.priority);
resetSum++;
case 4:
read();
readSum++;
case 5:
pop();
popSum++;
case 6:
finalize();
finalizeSum++;
default:
cout<<"Cannot Process Command :" + case + node.element + node.priority + ": wrong command";
}
}
cout << "\n";
cout << "\n";
cout << "================================================================";
cout << addSum << "total add commands processed.\n";
cout << deleteSum << "total delete commands processed.\n";
cout << resetSum << "total reset commands processed.\n";
cout << readSum << "total read commands processed.\n";
cout << popSum << "total pop commands processed.\n";
cout << finalizeSum << "total finalize commands processed.\n";
cout << totalSum << "total commands processed.\n";
}
|