Implementation of heap

Implementation of heap in C++ 

In this implementation of heap in C++, input of data is done in a specified method. The output data format is also pre-specified. In this sample C++ assignment, certain conditions have to be met while entering the input and in providing the output. Here, the expert is implementing a heap along with the percolate_up, percolate_down, and build_heap methods. Naming convention has not been changed to meet this criteria.

SOLUTION : –

#include “heap.h”

using namespace std;

int MaxHeap::pop() {

int value = values[0];

swap(0, values.size()-1);

values.pop_back();          // Delete last element, I had to add this to keep track of the size of the heap

percolate_down(0);

return value;

}

void MaxHeap::build_heap() {

for( int i = values.size() / 2; i >= 0; i–) {

percolate_down(i);

}

}

int MaxHeap::get_size(){

return values.size();

}

void MaxHeap::percolate_down(int index) {

int l = 2*index + 1;

int r = 2*index + 2;

int largest = index;

if(l < values.size() and values[l] > values[largest])

largest = l;

if(r < values.size() and values

[r]

> values[largest])

largest = r;

if(largest != index){

swap(index, largest);

percolate_down(largest);

}

}

void MaxHeap::percolate_up(int index) {

int parent = (index-1)/2;

if(parent >= 0 and values[parent] < values[index]){

swap(parent,index);

percolate_up(parent);

}

}

void MaxHeap::swap(int i, int j) {

int temp = values[i];

values[i] = values[j];

values[j] = temp;

}

#include <iostream>

#include <sstream>

#include <unordered_map>

#include <string>

#include <vector>

#include “heap.h”

using namespace std;

int main(int argc, char **argv) {

int k;

unordered_map< string, MaxHeap> table;

cin >> k;

string dummy;

getline(cin, dummy); // this swallows the newline after k

for(string line; getline(cin, line) && line.compare(“”); ) {

stringstream ss(line);

string name;

int score;

ss >> name;

ss >> score;

table[name].push_back(score);

}

double maxscore = -1;

string maxuser = “nobody”;

for( auto pair: table ) {

// int somevalue = 0;

// cout << pair.first << “: “;

// for( int i: pair.second ) {

//     cout << i << ” “;

// }

double avg_score = -1;

if(pair.second.get_size() >= k){

avg_score = 0;

pair.second.build_heap();               // Build heap of the scores

for(int i = 0; i < k; i++)

avg_score += pair.second.pop();     // Pick top k, find avg

avg_score = avg_score/k;

// cout << avg_score << endl;

if( avg_score > maxscore){

maxuser = pair.first;

maxscore = avg_score;

}

}

}

cout << maxuser << endl;;

return 0;

}