c++ - 堆排序 C++ 调试

问题描述

我的堆排序不正确并给出错误的输出。我想我已经完成了所有步骤，还有什么我遗漏的吗？

我很确定我的 heapify 方法，但我不知道 heapsort 方法上的循环。

#include <iostream>
using namespace std;

void swap(int* a, int* b) // swap using swap(&var1, &var2)
{
    int c = *a;
    *a = *b;
    *b = c;
}

void heapify(int arr[], int size)
{
    // For some reason others have a third parameter for heapify "i", or "max".

    // DECLARE VARIABLES
    int i;
    // int left = (2*i) + 1;
    // int right = (2*i) + 2;
    int parent = (i-1)/2;

    // Loop through entire array, check parent, then test
    for(i = size-1; i>1; i--) {         
        if(arr[i] > arr[parent]) {      
            swap(arr[i], arr[parent]);
            // Assuming that the swap is complete
        }
    }
    // Looks array from bottom to top, guarantees highest at the top
}

void heapsort(int arr[], int size)
{
    heapify(arr, 5);
    for(int i=size-1; i>=0; i--) { // i > 0 and i >= 0 is the same?
        swap(arr[0], arr[i]);
        heapify(arr, i);
    }
}

int main ()
{
    int arr[5] = {2,4,6,1,9};

    heapsort(arr, 5);
    for(int i=0; i<5; i++) {
        cout<<arr[i]<<" ";
    }
    return 0;
}

标签： c++arrayssortingheapsort

Heapify 对以第 i 个节点为根的子树进行排序，这就是您提到的第三个参数。参数i传递给heapify()from heapSort()，然后在内部使用heapify()。此外，leftandright在您的代码中被注释掉，因此您的代码不会检查子节点是否大于父节点。看看这个实现：

#include <iostream>

using namespace std;

void heapify(int* arr, int n, int i) // To heapify a subtree rooted with node i which is an index in arr[]. n is size of heap
{
    int largest = i; // Initialize largest as root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // If largest is not root
    if (largest != i)
    {
        swap(arr[i], arr[largest]);

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

int* heapSort(int* arr, int n) // uses heapify returns pointer to sorted array
{
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // One by one extract an element from heap
    for (int i = n - 1; i >= 0; i--)
    {
        // Move current root to end
        swap(arr[0], arr[i]);

        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }

    return arr;
}

int main()
{
    int arr[] = {3, 6, 1, 3, 2, 9, 7, 8, 5, 6, 4, 9, 2 };

    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Unsorted numbers: \n";
    print_array(arr, n);

    cout << "Sorted array: \n";
    int* sorted_array = heapSort(arr, n);
    print_array(sorted_array, n);

    return 0;
}

c++ - 堆排序 C++ 调试

问题描述

解决方案

推荐阅读