堆排序从介绍到使用向量的 C++ 实现中的算法

Question

我一直在研究 C++ 中的堆排序函数，它遵循我们 class 书中算法介绍第 3 版的逻辑，但没有得到所需的输出。一直在脑海中解决这个问题并且很接近，但我没有看到我的错误。我正在使用向量并省略了从单独的文本文件中读取值的代码。

关于我在每个版本中的索引哪里出了问题有什么想法吗？添加，我用来测试的输入列表是 10 15 8 3 16 20 11 12 5 7 4 1 19 13 2 6 9 14 17 18.

我尝试的第一种方法更接近本书，但给出的输出是 10 19 20 15 17 16 11 12 13 9 18 14 8 7 6 4 3 2 5 1 .如果我能弄清楚我是如何弄乱索引的，这是我的首选解决方案。

void maxHeapify(vector<int>&);
void buildMaxHeap(vector<int>&);
void heapSort(vector<int>&);

int main(int argc, char * argv[])
{
if (argc <= 1)
{
    std::cerr << "A file was not found or is not accessable." << std::endl;
    return (1);
}

vector<int> list;
int loc;

ifstream fin(argv[1]);

while (fin >> loc)
{
    list.push_back(loc);
}

// print unsorted list
cout << "Unsorted List:\n";
for (int i = 0; i < list.size(); ++i)
    cout << list[i] << ' ';
cout << endl;

heapSort(list);

// print sorted list
cout << "Sorted List:\n";
for (int i = 0; i < list.size(); ++i) {
    cout << list[i] << " ";
}
cout << endl;

cin.get();

return(0);
}

/* Heap Sort from Textbook using Vectors ***********************************/
void maxHeapify(vector<int>& A, int i)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= A.size()) && (A[l] > A[i]))
    largest = l;
else
    largest = i;

if ((r <= int(A.size())) && (A[r] > A[largest]))
    largest = r;

if (largest != i)
{
    swap(A[i], A[largest]);
    maxHeapify(A, largest);
}
}

void buildMaxHeap(vector<int>& A)
{
for (int i = int((A.size()-1) / 2); i >= 1; i--)  
{
    maxHeapify(A, i);
}
}

void heapSort(vector<int>& A)
{

buildMaxHeap(A);
for (int i = int(A.size()-1); i >= 2; i--)  
    swap(A[1], A[i]);
    maxHeapify(A, 1);
}
}

我尝试的第二种方法以随机排序的输出 2 1 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 到 50 结束50 个整数的列表，但在仅 20 个随机整数的列表上是正确的。代码如下：

void maxHeapify(vector<int>&, int, int);
void buildMaxHeap(vector<int>&, int);
void heapSort(vector<int>&, int);

int main(int argc, char * argv[])
{
if (argc <= 1)
{
    std::cerr << "A file was not found or is not accessable." << std::endl;
    return (1);
}

vector<int> list;
int loc;

ifstream fin(argv[1]);

while (fin >> loc)
{
    list.push_back(loc);
}

// print unsorted list
cout << "Unsorted List:\n";
for (int i = 0; i < list.size(); ++i)
    cout << list[i] << ' ';
cout << endl;

clock_t begin = clock();

heapSort(list, int(list.size() - 1));

clock_t end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;  //only reports in seconds, need to replace.  

printf("Heap Sort Elasped time is %0.6f seconds.", elapsed_secs);
cout << endl;

// print sorted list
cout << "Sorted List:\n";
for (int i = 0; i < list.size(); ++i) {
    cout << list[i] << " ";
}
cout << endl;

cin.get();

return(0);
}

/* Heap Sort from Textbook using Vectors ***********************************/
void maxHeapify(vector<int>& A, int i, int n)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= n) && (A[l - 1] > A[i - 1]))
    largest = l;
else
    largest = i;

if ((r <= n) && (A[r - 1] > A[largest - 1]))
    largest = r;

if (largest != i)
{
    swap(A[i - 1], A[largest - 1]);
    maxHeapify(A, largest, n);
}
}

void buildMaxHeap(vector<int>& A, int n)
{
for (int i = n / 2; i >= 1; i--)
{
    maxHeapify(A, i, n);
}
}

void heapSort(vector<int>& A, int n)
{

buildMaxHeap(A, n);
for (int i = n; i >= 2; i--)
{
    swap(A[0], A[i]);
    maxHeapify(A, 1, i - 1);
}
}

Answer 1

书中提供的算法将索引视为1,2,3....N，它们从1开始。

所以只要遵循算法但记住一件事当我们访问数组时，我们必须从索引中减去 1

所以你的第一个方法代码应该是：

void maxHeapify(vector<int>& A, int i, int n)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= n) && (A[l-1] > A[i-1]))
    largest = l;
else
    largest = i;

if ((r <= n) && (A[r-1] > A[largest-1]))
    largest = r;

if (largest != i)
{
    swap(A[i-1], A[largest-1]);
    maxHeapify(A, largest, n);
}
}

在第二种方法中，您做错的是您正在检查基于 0 的索引.

的边界

我们不能在此处使用基于 0 的索引，因为对于 0 索引，左侧 child 位于索引 1，但 2*0 仅是 0，因此 唯一的方法是在所有地方使用基于 1 的索引，并且仅在访问您减去的元素时使用 - 1

Answer 2

我最终解决了索引问题。由于我使用指针指向 A 并且大小永远不正确，我仍然无法使用第一种方法。所以我坚持使用第二种方法。这是更正后的代码。

void maxHeapify(vector<int>&, int, int);
void buildMaxHeap(vector<int>&, int);
void heapSort(vector<int>&, int);

int main(int argc, char * argv[])
{
if (argc <= 1)
{
    std::cerr << "A file was not found or is not accessable." << std::endl;
    return (1);
}

vector<int> list;
int loc;

ifstream fin(argv[1]);

while (fin >> loc)
{
    list.push_back(loc);
}

// print unsorted list
//cout << "Unsorted List:\n";
//for (int i = 0; i < list.size(); i++)
//  cout << list[i] << ' ';
//cout << endl;

clock_t begin = clock();

heapSort(list, int(list.size() - 1));

clock_t end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;  //only reports in seconds, need to replace.  

printf("Heap Sort Elasped time is %0.6f seconds.", elapsed_secs);
cout << endl;

// print sorted list
//cout << "Sorted List:\n";
//for (int i = 0; i < list.size(); i++) {
//  cout << list[i] << " ";
//}
//cout << endl;

cin.get();

return(0);
}

/* Heap Sort from Textbook using Vectors ***********************************/
void maxHeapify(vector<int>& A, int i, int n)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= n) && (A[l - 1] > A[i - 1]))
    largest = l;
else
    largest = i;

if ((r <= n) && (A[r - 1] > A[largest - 1]))
    largest = r;

if (largest != i)
{
    swap(A[i - 1], A[largest - 1]);
    maxHeapify(A, largest, n);
}
}

void buildMaxHeap(vector<int>& A, int n)
{
for (int i = n / 2; i >= 1; i--)
{
    maxHeapify(A, i, n);
}
}

void heapSort(vector<int>& A, int n)
{

buildMaxHeap(A, n);
for (int i = n; i >= 1; i--) // Remove last element from heap
{
    swap(A[0], A[i]);
    maxHeapify(A, 1, i); // Heapify reduced heap
}
}

堆排序从介绍到使用向量的 C++ 实现中的算法

Heap Sort from Intro to Algorithms in C++ Implementation using Vectors

c++

sorting

algorithm

vector

heapsort