массивы — Реализация минимальной кучи без STL и класса в переполнении стека

Question

массивы — Реализация минимальной кучи без STL и класса в переполнении стека

Я должен прочитать все данные (целые числа) из файла в массив, а затем выполнить итерацию массива, чтобы создать минимальную кучу, и добавить их после последнего элемента текущей кучи. После чтения в массив я должен позвонить SiftUp() на каждом элементе, что означает перемещение int в правильную позицию в массиве. Кроме того, я должен посчитать целые числа, когда я их читаю, и установить для этого глобальный размер кучи.
В конце всех входов я пытаюсь распечатать первые пять элементов массива min heap. вывод неверный. Мой код не создает минимальной кучи, поэтому вывод случайный. Что не так с логикой?

входной файл имеет 97 целых чисел:

347
765
654
44
15
567
098
//and so on

выход:

Please enter the name of the file to open :data.txt
at index 1 :284
at index 2 :870
at index 3 :319
at index 4 :47
at index 5 :312
at index 1 :284    // i dont know why it started again
at index 2 :870
at index 3 :319
at index 4 :47
at index 5 :312     //stops here

моя программа:

using namespace std;

int heapSize;
void SiftUp(int arr[], int heapSize);
const int arr_Size=100;
int heapArr[arr_Size];
void minHeap(int heapArr[]);

int main()
{
int integers;
string fileName;
ifstream infile;
cout << "Please enter the name of the file to open :";
cin >> fileName;
infile.open(fileName.c_str());
if(!infile)
{
cerr << "An eror occurred while openieng the file.";
exit(1);
}
while(!infile.eof())
{

for (int i=0; i<arr_Size; i++){
infile >> integers;
heapArr[i]=integers;
heapSize=i;
}
}
infile.close();
minHeap(heapArr);
for (int count =1 ; count <=5 ; count ++)
{
cout << " Min at index " << count  <<" :"<< heapArr[count] << endl;
}
return 0;
}

void SiftUp(int arr[], int heapSize)
{
int p;
if (heapSize==1) return;
else p = heapSize/2;
if (arr[p] > arr[heapSize]) return;
else swap (arr[heapSize],arr[p]);
SiftUp(arr, p);
}

void minHeap(int arr[])
{
for (int i=0; i <arr_Size ; i++){
SiftUp(arr, heapSize);
}
}

-4

arrays c++heap min-heap

Решение

Другие решения

using namespace std;

int heapSize;
const int arr_Size=100;
int heapArr[arr_Size];
int main()
{
int integers;
string fileName;
ifstream infile;
cout << "Please enter the name of the file to open :";
cin >> fileName;
infile.open(fileName.c_str());
if(!infile)
{
cerr << "An eror occurred while openieng the file.";
exit(1);
}
while(!infile.eof())
{

for (int i=0; i<arr_Size; i++){
infile >> integers;
heapArr[i]=integers;
heapSize=i;
}

infile.close();
build_minheap(heapArr,heapSize);
for (int count =1 ; count <=5 ; count ++)
{
cout << " Min at index " << count  <<" :"<< heapArr[count] << endl;
}
return 0;
}

void min_heapify(int *a,int i,int n)
{
int j, temp;
temp = a[i];
j = 2 * i;
while (j <= n)
{
if (j < n && a[j+1] < a[j])
j = j + 1;
if (temp < a[j])
break;
else if (temp >= a[j])
{
a[j/2] = a[j];
j = 2 * j;
}
}
a[j/2] = temp;
return;
}
void build_minheap(int *a, int n)
{
int i;
for(i = n/2; i >= 1; i--)
{
min_heapify(a,i,n);
}
}

1

Источник

Accepted Answer

Почему вы используете массивы для передачи в качестве параметров, которые уже определены глобально. Я пытался исправить ваш код. Посмотри и сделай как есть. Надеюсь, это сработает.

 int main()
{
int integer;
string fileName;
ifstream infile;
cout << "Please enter the name of the file to open :";
cin >> fileName;                                                  // asks user to     input filename
infile.open(fileName.c_str());                                    // opens file
if(!infile)
{
cerr << "An eror occurred while openieng the file.";
exit(1);
}
int i;
for (i=1; i<arr_Size; i++){
infile >> integer;
if(infile.fail())break;
heapArr[i]=integer;
SiftUp(i);
}
infile.close();
heapSize=i;
for (int count =1 ; count <=5 ; count ++)
{
cout << count  <<" :"<< heapArr[count] << endl;
}

return 0;
}

void SiftUp(int heapSize){
int p;
if (heapSize==1) return;
p = heapSize/2;
if (heapArr[p] < heapArr[heapSize]) return;
swap (heapArr[heapSize],heapArr[p]);
SiftUp(p);
}

1