如何将堆排序程序转换为使用 C++ 标准容器（例如 std::vector）？

Question

我知道如何用 C 编写代码，但是，这是我第一次尝试使用 C++。并且在 C++ 中不允许使用 VLA（可变长度数组）。那么我怎样才能将这个程序转换为使用 C++ 标准容器（例如 std::vector）而不是走 C 路线呢？

而不是 main() 中的 int arr[n];，使用 std::vector<int> arr(n);，我还需要做哪些进一步的改变？请协助。

这是我的代码，


#include<iostream>
 
using namespace std;
 
// A function to heapify the array.
void MaxHeapify(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;
        // Break if parent value is already greater than child value.
        if (temp > a[j])
            break;
        // Switching value with the parent node if temp < a[j].
        else if (temp <= a[j])
        {
            a[j/2] = a[j];
            j = 2*j;
        }
    }
    a[j/2] = temp;
    return;
}
void HeapSort(int a[], int n)
{
    int i, temp;
    for (i = n; i >= 2; i--)
    {
        // Storing maximum value at the end.
        temp = a[i];
        a[i] = a[1];
        a[1] = temp;
        // Building max heap of remaining element.
        MaxHeapify(a, 1, i - 1);
    }
}
void Build_MaxHeap(int a[], int n)
{
    int i;
    for(i = n/2; i >= 1; i--)
        MaxHeapify(a, i, n);
}
int main()
{
    int n, i;
    cout<<"\nEnter the number of data element to be sorted: ";
    cin>>n;
    n++;
    int arr[n];
    for(i = 1; i < n; i++)
    {
        cout<<"Enter element "<<i<<": ";
        cin>>arr[i];
    }
    // Building max heap.
    Build_MaxHeap(arr, n-1);
    HeapSort(arr, n-1);
 
    // Printing the sorted data.
    cout<<"\nSorted Data ";
 
    for (i = 1; i < n; i++)
        cout<<"->"<<arr[i];
    cout<<"\nTime Complexity: Best case = Avg case = Worst case = O(n logn)";
 
    return 0;
}

Answer 1

And the use of VLAs(Variable Length Arrays) is not allowed in C++

我刚刚用 C++ 编译了您的代码，它运行得非常好。如果您认为我误解了您，请随时改写。如果你想坚持使用数组而不是 std::vector，你可以使用 std::array。否则在你的情况下，它主要是将 int[] 换成 vector<int> 和函数参数中的 &。

如何将堆排序程序转换为使用 C++ 标准容器（例如 std::vector）？

How can I convert my heap sort program to use C++ standard containers (for example std::vector)?

c++

arrays

c

stl

heapsort