0

我正在尝试使用算法简介中给出的算法构建一个最大堆，但我无法让它工作。首先，我在函数之间传递数组时遇到了一些有趣的问题。我的理解是在 C++ 中数组是通过引用传递的，但是在我传递一个数组之后，我检查了参数的地址和它们不匹配的参数。当我尝试在作为参数的数组上使用 sizeof() 时，它不会返回正确的值。

其次，该算法似乎不起作用。它确实对数组进行了一些更改，并使数字更接近堆，但仍有一段路要走。我已经检查了几十次代码，它似乎与我的文本中给出的伪代码一致。我错过了什么？

#include <iostream>
#include <ctime>

#define N 10
#define DISPLAY

using namespace std;


// Display an array
void display(double p[]) {
#ifdef DISPLAY
    for (int i = 0; i < N; i++) cout << p[i] << " ";
    cout << endl;
#endif
}


inline int parent(int i)
{return i/2;}

inline int left(int i)
{return 2*i;}

inline int right(int i)
{return 2*i+1;}

void maxHeapify(double p[], int i)
{
    int largest;

   int l = left(i);
   int r = right(i);

   if (l <= N && (p[l] > p[i]))
        largest = l;

    else
        largest = i;

    if (r <= N && (p[r] > p[largest]))
        largest = r;

    if (largest != i)
    {
        double temp = p[i];

        p[i] = p[largest];

        p[largest] = temp;

        maxHeapify(p, largest);
    }
}   

void buildMaxHeap(double p[])
{
    for (int i=N/2; i>0; i--)
        maxHeapify(p, i);
}

int main() {
 double a[] = {4,1,3,2,16,9,10,14,8,7};
 buildMaxHeap(a);
 display(a);
}
4

1 回答 1

0

我修改了你的代码如下：

#include <iostream>
#include <ctime>

#define N 10
#define DISPLAY

using namespace std;


// Display an array
void display(double p[]) {
#ifdef DISPLAY
    for (int i = 0; i < N; i++) cout << p[i] << " ";
    cout << endl;
#endif
}


inline int parent(int i)
{return i/2;}

inline int left(int i)
{return 2*i;}

inline int right(int i)
{return 2*i+1;}

void maxHeapify(double p[], int i)
{
    int largest;

   int l = left(i)-1;
   int r = right(i)-1;
   i=i-1;

   if (l <= N && (p[l] > p[i]))
        largest = l;

    else
        largest = i;

    if (r <= N && (p[r] > p[largest]))
        largest = r;

    if (largest != i)
    {
        double temp = p[i];

        p[i] = p[largest];

        p[largest] = temp;

        maxHeapify(p, largest+1);
    }
}   

void buildMaxHeap(double p[])
{
    for (int i=N/2; i>0; i--)
        maxHeapify(p, i);
}

int main() {
 double a[] = {4,1,3,2,16,9,10,14,8,7};
 buildMaxHeap(a);
 display(a);
}
于 2013-02-23T22:12:44.210 回答