在 C++ 中实现没有 STL 和类的最小堆

Question

我必须将文件中的所有数据（整数）读入数组，然后迭代数组以生成最小堆并将它们添加到当前堆的最后一个元素之后。读入数组后，我必须在每个元素上调用 SiftUp()，这意味着将 int 移动到数组中的正确位置。另外，我必须在读取整数时计算整数并将全局 heapSize 设置为其。在所有输入的末尾，我试图打印出最小堆数组的前五个元素。输出错误。我的代码没有生成任何最小堆，这就是为什么输出是随机的。逻辑有什么问题？

输入文件有 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);
    }
}

Answer 1

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);
     }
 }

Answer 2

为什么要使用数组作为已全局定义的参数进行传递。我试图修复您的代码。照原样去做。希望，它会起作用。

 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);
}

在 C++ 中实现没有 STL 和类的最小堆

Implementing minimum heap without STL and classess in C++

c++

arrays

heap

min-heap