C++/ JAVA You\'ll be given a list of students, and you\'ll need to sort it using
ID: 3747229 • Letter: C
Question
C++/ JAVA
You'll be given a list of students, and you'll need to sort it using heap sort. We want to sort the students according to graduation year (soonest first), and for students with the same graduation year, alphabetically by first name (and if there are any students with the same first name and graduation year, ties should be broken by last name). However, rather than just printing the final sorted list, you'll print the list after it has been converted to a heap and the partially sorted list after each call to extractMax.
The first line of the input consists of an integer, n, indicating the number of words you'll need to sort. The next n lines will each consist of student data wtih space-separated first name, last name, and graduation year, in that order. The input will terminate with a blank line. For example:
Explanation / Answer
#include<iostream>
#include<vector>
using namespace std;
typedef struct student{
string first;
string last;
int year;
}st;
void swap(vector <st>&a,int i ,int j){
st temp=a[i];
a[i]=a[j];
a[j]=temp;
}
void heapify(vector<st> &arr,int i ,int n){
int left=2*i+1;
int right=2*i+2;
int max=i;
if(left<n){
if(arr[left].year>arr[max].year)max=left;
else if(arr[left].year==arr[max].year){
if(arr[left].first>arr[max].first)max=left;
else if(arr[left].first==arr[max].first ){
if(arr[left].last>arr[max].last)max=left;
}
}
}
if(right<n){
if(arr[right].year>arr[max].year)max=right;
else if(arr[right].year==arr[max].year){
if(arr[right].first>arr[max].first)max=right;
else if(arr[right].first==arr[max].first ){
if(arr[right].last>arr[max].last)max=right;
}
}
}
if(max!=i){
swap(arr,i,max);
heapify(arr,max,n);
}
}
void constructHeap(vector <st > &arr){
int i,j,num=arr.size();
for(i=num/2-1;i>=0;i--)
heapify(arr,i,num);
}
void heapsort (vector <st > &arr){
int j,num=arr.size();
for(j=num-1;j>=0;j--){
cout<<arr[0].first<<" "<<arr[0].last<<" "<<arr[0].year;
arr[0]=arr[num-1];
arr.pop_back();
heapify(arr,0,j);
}
}
int main(){
int n;
cin>>n;
st s[n];
vector <st> arr;
for(int i=0;i<n;i++){
cin>>s[i].first>>s[i].last>>s[i].year;
arr.push_back(s[i]);
}
constructHeap(arr);
heapsort(arr);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.