12529 - Tsai DS 20191128 Heap Sort
|
Time |
Memory |
| Case 1 |
1 sec |
32 MB |
| Case 2 |
1 sec |
32 MB |
| Case 3 |
1 sec |
32 MB |
Description
Please complete Max Heap data structure with array and implement the Heap Sort with the Max Heap data structure.
You can reference the following framework providing by TA.
#include <iostream>
using namespace std;
void swap(int &p1, int &p2){
int temp = p1;
p1 = p2;
p2 = temp;
}
void PrintArr(int arr[], int len){
for(int i=1; i<=len; i++){
cout << arr[i] << " ";
}
cout << endl;
}
void MaxHeapify(int arr[], int root, int len){
}
void BuildMaxHeap(int arr[], int len){
}
void HeapSort(int arr[], int len){
// You need to print out the heap after building the initial heap
BuildMaxHeap(arr, len);
PrintArr(arr, len);
}
int main(){
int arr[1000];
int len;
cin >> len;
for(int i=1; i<=len; i++){
cin >> arr[i];
}
// Print out the heap after sorting
HeapSort(arr, len);
PrintArr(arr, len);
return 0;
}
Input
The first line of input data is the total size of the input data.
The secone line of the input data is the data that you need to sort.
Output
The first line of output is the result of initial heap after buiding heap function.
The second line of the output is the result being sorted.
Tags