I'm having trouble figuring out why my extractMax function isn't working correctly. I'm reading from an input file that looks something like this:
(arule, 12), (brule, 21), (zrule, 70), (drule, 25), (erule, 10)
(frule, 3)
(grule, 20), (srule, 100)
It should read the priorities into an array, build the heap, and then extract the max priority. It seems to work until it reads the third line and tries to extract max. Here's my code:
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
int A[300];
int index = 0, z;
int parent(int i){
return i/2;
}
int left(int i){
return 2*i;
}
int right(int i){
return (2*i)+1;
}
void swap(int &a,int &b){
int temp;
temp=a;
a=b;
b=temp;
}
void heapify(int A[], int i, int size){
int largest = 0;
int l = left(i);
int r = right(i);
if((l <= index) && (A[l] > A[i])){
largest = l;
}
else largest = i;
if((r <= index) && (A[r] > A[largest]))
largest = r;
if(largest != i){
swap(A[i], A[largest]);
heapify(A, largest, index);
}
}
void write(int p1,int p2,int p3)
{
if(p2 == -1){
A[index]=p1;
index++;
}
else if(p3 == -1){
p1=p1*10;
A[index]=p1+p2;
index++;
}
else{
p1=p1*100;
p2=p2*10;
A[index]=p1+p2+p3;
index++;
}
}
void buildHeap(int A[], int size){
for(int i = (index/2); i >= 0; --i)
heapify(A, i, index);
}
int extractMax(int A[], int size){
/*
if(index < 1) return 0;
else{
int max = 0;
max = A[0];
A[0] = A[index];
heapify(A, 1, index);
return max;
}*/
int temp = A[0];
A[0] = A[index];
A[index] = temp;
heapify(A, 0, index);
}
void insert(int A[], int x, int size){
index = index + 1;
int i = index;
while((i > 1) && (A[i/2] < x)){
A[i] = A[i/2];
i = i/2;
}
A[i] = x;
}
using namespace std;
int main(){
for(z=0; z<300 ; z++){
A[z]=-1;
}
string str;
int p1 = -1, p2 = -1, p3 = -1;
bool comma=false, left=false;
char current;
ifstream infile;
infile.open("input.txt");
while(!infile.eof()){
getline(infile, str);
for(int aux=0; aux < str.length(); aux++){
current = str.at(aux);
if(current == ')'){
left = false;
comma = false;
write(p1,p2,p3);
p1 = -1;
p2 = -1;
p3 = -1;
}
else{
if(current == '(')
left = true;
else if((current == ',')&& left)
comma = true;
else if(comma && left && ((current>47) && (current<58))){
if(p1 == -1)
p1 = current - 48;
else if(p2 == -1)
p2 = current - 48;
else p3 = current - 48;
}
}
}
for(int zz=0;zz<300;zz++){
if(A[zz] == -1) break;
cout<<A[zz]<<" ";
cout<<index<<endl;
}
cout<<endl;
buildHeap(A, index);
for(int zz=0;zz<300;zz++){
if(A[zz] == -1) break;
cout<<A[zz]<<" ";
cout<<index<<endl;
}
extractMax(A, index);
cout<<endl;
}
system("pause");
return 0;
}
Any help is appreciated.