Sorting Height and Storing in Binary Tree Assignment
Algorithm
Write a C++ assignment program describing a line of N students standing in a row. Each line of the file gives the name of a student and their integer height. We’ll be implementing the algorithm that sweeps downward. In particular, the main steps are:-
Read the input into a vector, where the string part is a student’s name and the int part is their height
Build a second vector, where the first part is height and the second part is their index
Sort the contents of this second vector (in order by height)
For each student in decreasing order of height
Add a student to a balanced BST keyed on the index (a set)
For each student, call the find method to get an iterate pointing to their record in the set.
Solution:
#include < iostream>
#include < vector>
#include < set>
#include < cstdlib>
using namespace std;
int main() {
vector> students;
string data;
getline(cin, data);
while(!data.empty()) {
students.emplace_back(data.substr(0, data.find(' ')), stoi(data.substr(data.find(' ') + 1, data.size())));
getline(cin, data);
}
vector> heightsByIndex;
for(int i = 0; i < students.size(); i++) {
heightsByIndex.emplace_back(students[i].second, i);
}
sort(heightsByIndex.begin(), heightsByIndex.end());
set bstOfIndex;
int maxDiff = 0;
int prevIndex = 0;
int nextIndex = 0;
for(int i = heightsByIndex.size() - 1; i >= 0; i--) {
bstOfIndex.insert(heightsByIndex[i].second);
set::iterator pos = bstOfIndex.find(heightsByIndex[i].second);
if(pos != bstOfIndex.begin()) {
int diff = abs(*pos - *prev(pos, 1));
if(maxDiff < diff) {
maxDiff = diff;
prevIndex = *pos;
nextIndex = *prev(pos, 1);
}
}
if(next(pos, 1) != bstOfIndex.end()) {
int diff = abs(*pos - *next(pos, 1));
if(maxDiff < diff) {
maxDiff = diff;
prevIndex = *pos;
nextIndex = *next(pos, 1);
}
}
}
cout << "Longest sight : " << maxDiff << endl << "People : " << students[prevIndex].first << " and " << students[nextIndex].first << endl;
}