如何将堆排序程序转换为使用 C++ 标准容器(例如 std::vector)?
How can I convert my heap sort program to use C++ standard containers (for example std::vector)?
我知道如何用 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;
}
And the use of VLAs(Variable Length Arrays) is not allowed in C++
我刚刚用 C++ 编译了您的代码,它运行得非常好。如果您认为我误解了您,请随时改写。
如果你想坚持使用数组而不是 std::vector
,你可以使用 std::array
。否则在你的情况下,它主要是将 int[]
换成 vector<int>
和函数参数中的 &
。
我知道如何用 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;
}
And the use of VLAs(Variable Length Arrays) is not allowed in C++
我刚刚用 C++ 编译了您的代码,它运行得非常好。如果您认为我误解了您,请随时改写。
如果你想坚持使用数组而不是 std::vector
,你可以使用 std::array
。否则在你的情况下,它主要是将 int[]
换成 vector<int>
和函数参数中的 &
。