Need help with the trickle down This is the maxheap.h #ifndef MAXHEAP_H_INCLUDED
ID: 3728744 • Letter: N
Question
Need help with the trickle down
This is the maxheap.h
#ifndef MAXHEAP_H_INCLUDED
#define MAXHEAP_H_INCLUDED
#include <vector>
#include <sstream>
#include <string>
#include <queue>
#include <cmath> // pow()
using namespace std;
#define PARENT(i) ((i-1) / 2)
#define LINE_WIDTH 60.0
template<class T>
class MaxHeap{
// private:
vector<T> heap;
void bubbleUp(int id);
void Heapify() {
int length = heap.size();
for(int i=length / 2 -1; i>=0; --i)
trickleDown(i);
};
public:
MaxHeap( vector<T> &vector ) : heap(vector) { Heapify(); } ;
MaxHeap() {};
void trickleDown(int id);
int size() { return heap.size() ; };
bool empty() { return heap.size() <= 0 ;};
bool clear() { heap.clear(); return(heap.size() <= 0); } ;
T GetMax() {return heap[0]; };
void remove();
void sort();
void add(T newValue);
bool replace(vector<T> array) {
heap.clear();
heap = array;
};
bool build(vector<T>array) {
heap = array;
Heapify();
};
string toString();
};
template<class T> // old blank 1
//bubble up class
void MaxHeap<T>::bubbleUp(int id){
if(id == 0) return;
int parentId = (id-1)/2;
if(heap[parentId] < heap[id]) {
T temp = heap[parentId];
heap[parentId] = heap[id];
heap[id] = temp;
bubbleUp(parentId);
}
}
template<class T>
void MaxHeap<T>::trickleDown(int id) {
int length = heap.size();
int leftChildIndex = 2*id + 1;
int rightChildIndex = 2*id + 2;
if(leftChildIndex >= length)
return; //index is a leaf
int minIndex = id;
if(heap[id] > heap[leftChildIndex])
{
minIndex = leftChildIndex;
}
if((rightChildIndex < length) && (heap[minIndex] > heap[rightChildIndex]))
{
minIndex = rightChildIndex;
}
if(minIndex != id)
{
//need to swap
auto temp = heap[id];
heap[id] = heap[minIndex];
heap[minIndex] = temp;
trickleDown(minIndex);
}
}
template<class T>
void MaxHeap<T>::remove(){
int length = heap.size();
if(length == 0) return;
heap[0] = heap[length - 1];
heap.pop_back();
trickleDown(0);
}
template<class T>
//sort function
void MaxHeap<T>::sort(){
int length = heap.size();
if(length == 0) return;
heap[0] = heap[length - 1];
for (int i=0;i<length-1;i++){
remove();
cout<<" "<<heap[0];
}
}
template<class T>
void MaxHeap<T>::add(T newValue) {
int length = heap.size();
heap.push_back(newValue);
bubbleUp(length);
}
template<class T>
string MaxHeap<T>::toString() {
stringstream ss;
int num_nodes = heap.size();
int print_pos[num_nodes];
int i; // node
int j; // node of level upto 1 2 4 8
int k; // letter in segment
int pos; // letter position of level
int x=1; //
int level=0;
char dash; // drawing symbol between left and right child
queue<string> line;
ss << "L1: "; // the left margin
print_pos[0] = 0;
dash = '-';
for(i=0,j=1; i<num_nodes; i++,j++) {
pos = print_pos[((i-1) / 2)]
+ ((i%2?-1:1)*(LINE_WIDTH/(pow(2,level+1))));
for (k=0; k<pos-x-1; k++) {
ss << (i==0||i%2?' ':dash);
line.push(" ");
}
ss << heap[i];
// draw the child link for last node
if((i==num_nodes-1) && (i%2==1))
for (k=0; k<(pos-x); k++) ss << dash;
line.push("|");
print_pos[i] = x = pos;
if (j==pow(2,level)) {
ss << " ";
while(!line.empty()) {
ss << line.front();
line.pop();
}
level++;
ss << " L" << level+1 << ": ";
x = 1; j = 0;
}
}
ss << " Heap Array: ";
int heap_size = heap.size();
for(auto str: heap){
ss << str << ((heap_size <= 1) ? " " : ", ");
heap_size--;
}
ss << " ";
return ss.str();
}
#endif // MAXHEAP_H_INCLUDED
This is the main.cpp
#include <iostream>
#include <vector>
#include "maxheap.h"
using namespace std;
bool trace = false; // Not good, but easier this way.
//print the menu
void menu() {
cout << " === HeapSort Test Menu === "
<< " TRACE is " << (trace?"ON ":"OFF ")
<< " new build a new heap by bulk adding "
<< " a (,) delimited list "
<< " add to heap "
<< " clear entire heap "
<< " remove from heap "
<< " view heap "
<< " sort by dumping out all items "
<< " trace toggle on/off "
<< " help "
<< " quit ";
}
//functions declarations
void parse(string input, vector<string> &tokens, string del);
int tokenSize(string input, string del);
void listing(vector<string> list);
int main( ) {
string del = ",";
vector<string> sorted;
vector<string> arr = {"3","q","D","1","4","B","8","9","z","s","0"};
cout << "You may build a Max-Heap with the alpha numeric letters, such as: ";
for(int i =0; i<arr.size(); i++) cout << arr[i] << (i<arr.size()-1?", ":" ");
MaxHeap<string> aHeap(arr);
cout << aHeap.toString(); //print the heap
cout << "The above Tree and Array are raw data for display purpose. "
<< " Use command-new or command-add to build a HEAP. ";
auto menu = []() {
cout << " === HeapSort Test Menu === "
<< " TRACE is " << (trace?"ON ":"OFF ")
<< " new build a new heap by bulk adding "
<< " a (,) delimited list "
<< " add to the heap "
<< " clear the entire heap "
<< " remove from the heap "
<< " view the entire heap "
<< " sort by dumping out all items "
<< " trace toggle on/off "
<< " help "
<< " quit ";
};
menu(); //call the menu
int tSize;
string input, answer;
while(true){
cout << " >--- Enter your choice -> ";
getline(cin, answer);
vector<string> tokens;
if( answer == "new") {
aHeap.clear();
cout << "New list: ";
getline(cin, input);
parse(input, tokens, del);
tSize = tokenSize(input,del);
cout << "List Size: " << tSize << " Inserting: ";
for(int i=0; i<tSize; i++)
cout << tokens[i] << (i<tSize-1?", ":" ");
if(trace) {
aHeap.replace(tokens);
for(int i=tokens.size() / 2 - 1; i>=0; --i){
cout << aHeap.toString();
aHeap.trickleDown(i);
cout << "check item " << i << " : ";
}
}
else aHeap.build( tokens ) ;
tokens.clear();
cout << aHeap.toString();
}
else if ( answer == "sort" ) {
cout<<" ";
aHeap.sort();
}
else if ( answer == "view" || answer == "show" ) {
cout << aHeap.toString();
}
else if ( answer == "add" ) {
string in;
cout << " Enter a new item: ";
cin >> in;
cin.ignore(1000,' ');
aHeap.add(in);
cout << aHeap.toString();
}
else if ( answer == "remove" ) {
aHeap.remove();
cout << aHeap.toString();
}
else if ( answer == "clear" ) { aHeap.clear(); }
else if ( answer == "trace" ) {
if(!trace) cout << "Trace mode is activated. " ;
else cout << "Trace mode is NOT activated. " ;
trace = !trace;
}
else if( answer == "help" || answer == "menu" ) menu();
else if( answer == "quit" ){
cout << endl << "GOOD BYE :) "<< endl;
break;
}
else
cout << endl<< "INVALID INPUT " ;
}
return 0;
}
//LISTING function
void listing(vector<string> list) {
int i = 0, size = list.size();
cout << "sorted: ";
for(auto item:list) {
i++;
cout << item << ((i < size)?", ":"");
}
cout << endl;
return;
}
//parse function
void parse(string input, vector<string> &tokens, string del)
{
tokens.clear();
int countDel =0;
for(int i = 0; i< input.length(); i++){
if(input[i] == del[0])
countDel++;
}
int tokenSize = countDel +1;
for(int i=0; i< tokenSize; i++){
int x= input.find(del[0]);
tokens.push_back(input.substr(0,x));
input = input.substr(x+1);
}
}
//tokensize function
int tokenSize(string input, string del)
{
int size;
int countDel =0;
for(int i = 0; i< input.length(); i++){
if(input[i] == del[0])
countDel++;
}
return size = countDel + 1;
}
Current Output:
Need an output like this:
Explanation / Answer
here is your modified code : --------------->>>>>>>>>>>
#ifndef MAXHEAP_H_INCLUDED
#define MAXHEAP_H_INCLUDED
#include <vector>
#include<iostream>
#include <sstream>
#include <string>
#include <queue>
#include <cmath> // pow()
using namespace std;
#define PARENT(i) ((i-1) / 2)
#define LINE_WIDTH 60.0
template<class T>
class MaxHeap{
// private:
vector<T> heap;
void bubbleUp(int id);
void Heapify() {
int length = heap.size();
for(int i=length / 2 -1; i>=0; --i)
trickleDown(i);
};
public:
MaxHeap( vector<T> &vector ) : heap(vector) { Heapify(); } ;
MaxHeap() {};
void trickleDown(int id);
int size() { return heap.size() ; };
bool empty() { return heap.size() <= 0 ;};
bool clear() { heap.clear(); return(heap.size() <= 0); } ;
T GetMax() {return heap[0]; };
void remove();
void sort();
void add(T newValue);
bool replace(vector<T> array) {
heap.clear();
heap = array;
};
bool build(vector<T>array) {
heap = array;
Heapify();
};
string toString();
};
template<class T> // old blank 1
//bubble up class
void MaxHeap<T>::bubbleUp(int id){
if(id == 0) return;
int parentId = (id-1)/2;
if(heap[parentId] < heap[id]) {
T temp = heap[parentId];
heap[parentId] = heap[id];
heap[id] = temp;
bubbleUp(parentId);
}
}
template<class T>
void MaxHeap<T>::trickleDown(int id) {
int length = heap.size();
int leftChildIndex = 2*id + 1;
int rightChildIndex = 2*id + 2;
if(leftChildIndex >= length)
return; //index is a leaf
int minIndex = id;
if(heap[id] > heap[leftChildIndex])
{
minIndex = leftChildIndex;
}
if((rightChildIndex < length) && (heap[minIndex] > heap[rightChildIndex]))
{
minIndex = rightChildIndex;
}
if(minIndex != id)
{
//need to swap
auto temp = heap[id];
heap[id] = heap[minIndex];
heap[minIndex] = temp;
trickleDown(minIndex);
}
}
template<class T>
void MaxHeap<T>::remove(){
int length = heap.size();
if(length == 0) return;
heap[0] = heap[length - 1];
heap.pop_back();
trickleDown(0);
}
template<class T>
//sort function
void MaxHeap<T>::sort(){
int length = heap.size();
if(length == 0) return;
heap[0] = heap[length - 1];
for (int i=0;i<length-1;i++){
remove();
cout<<" "<<heap[0];
}
}
template<class T>
void MaxHeap<T>::add(T newValue) {
int length = heap.size();
heap.push_back(newValue);
bubbleUp(length);
}
template<class T>
string MaxHeap<T>::toString() {
stringstream ss;
int num_nodes = heap.size();
int print_pos[num_nodes];
int i; // node
int j; // node of level upto 1 2 4 8
int k; // letter in segment
int pos; // letter position of level
int x=1; //
int level=0;
char dash; // drawing symbol between left and right child
queue<string> line;
ss << "L1: "; // the left margin
print_pos[0] = 0;
dash = '-';
for(i=0,j=1; i<num_nodes; i++,j++) {
pos = print_pos[((i-1) / 2)]
+ ((i%2?-1:1)*(LINE_WIDTH/(pow(2,level+1))));
for (k=0; k<pos-x-1; k++) {
ss << (i==0||i%2?' ':dash);
line.push(" ");
}
ss << heap[i];
// draw the child link for last node
if((i==num_nodes-1) && (i%2==1))
for (k=0; k<(pos-x); k++) ss << dash;
line.push("|");
print_pos[i] = x = pos;
if (j==pow(2,level)) {
ss << " ";
while(!line.empty()) {
ss << line.front();
line.pop();
}
level++;
ss << " L" << level+1 << ": ";
x = 1; j = 0;
}
}
ss << " Heap Array: ";
int heap_size = heap.size();
for(auto str: heap){
ss << str << ((heap_size <= 1) ? " " : ", ");
heap_size--;
}
ss << " ";
return ss.str();
}
#endif
This is the main.cpp: ------------------>>>>>>>>>>
#include <iostream>
#include <vector>
#include "maxheap.h"
using namespace std;
bool trace = false; // Not good, but easier this way.
//print the menu
void menu() {
cout << " === HeapSort Test Menu === "
<< " TRACE is " << (trace?"ON ":"OFF ")
<< " new build a new heap by bulk adding "
<< " a (,) delimited list "
<< " add to heap "
<< " clear entire heap "
<< " remove from heap "
<< " view heap "
<< " sort by dumping out all items "
<< " trace toggle on/off "
<< " help "
<< " quit ";
}
//functions declarations
void parse(string input, vector<string> &tokens, string del);
int tokenSize(string input, string del);
void listing(vector<string> list);
int main( ) {
string del = ",";
vector<string> sorted;
vector<string> arr = {"3","q","D","1","4","B","8","9","z","s","0"};
cout << "You may build a Max-Heap with the alpha numeric letters, such as: ";
for(int i =0; i<arr.size(); i++) cout << arr[i] << (i<arr.size()-1?", ":" ");
MaxHeap<string> aHeap(arr);
cout << aHeap.toString(); //print the heap
cout << "The above Tree and Array are raw data for display purpose. "
<< " Use command-new or command-add to build a HEAP. ";
auto menu = []() {
cout << " === HeapSort Test Menu === "
<< " TRACE is " << (trace?"ON ":"OFF ")
<< " new build a new heap by bulk adding "
<< " a (,) delimited list "
<< " add to the heap "
<< " clear the entire heap "
<< " remove from the heap "
<< " view the entire heap "
<< " sort by dumping out all items "
<< " trace toggle on/off "
<< " help "
<< " quit ";
};
menu(); //call the menu
int tSize;
string input, answer;
while(true){
cout << " >--- Enter your choice -> ";
getline(cin, answer);
vector<string> tokens;
if( answer == "new") {
aHeap.clear();
cout << "New list: ";
getline(cin, input);
parse(input, tokens, del);
tSize = tokenSize(input,del);
cout << "List Size: " << tSize << " Inserting: ";
for(int i=0; i<tSize; i++)
cout << tokens[i] << (i<tSize-1?", ":" ");
if(trace) {
aHeap.replace(tokens);
for(int i=tokens.size() / 2 - 1; i>=0; --i){
cout << aHeap.toString();
aHeap.trickleDown(i);
cout << "check item " << i << " : ";
}
}
else aHeap.build( tokens ) ;
tokens.clear();
cout << aHeap.toString();
}
else if ( answer == "sort" ) {
cout<<" ";
if(!trace){
aHeap.sort();
}else{
vector<string> list;
int s = aHeap.size();
for(int i = 0;i<s-1;i++){
aHeap.remove();
list.push_back(aHeap.GetMax());
listing(list);
cout<<aHeap.toString();
}
listing(list);
}
}
else if ( answer == "view" || answer == "show" ) {
cout << aHeap.toString();
}
else if ( answer == "add" ) {
string in;
cout << " Enter a new item: ";
cin >> in;
cin.ignore(1000,' ');
aHeap.add(in);
cout << aHeap.toString();
}
else if ( answer == "remove" ) {
aHeap.remove();
cout << aHeap.toString();
}
else if ( answer == "clear" ) { aHeap.clear(); }
else if ( answer == "trace" ) {
if(!trace) cout << "Trace mode is activated. " ;
else cout << "Trace mode is NOT activated. " ;
trace = !trace;
}
else if( answer == "help" || answer == "menu" ) menu();
else if( answer == "quit" ){
cout << endl << "GOOD BYE :) "<< endl;
break;
}
else
cout << endl<< "INVALID INPUT " ;
}
return 0;
}
//LISTING function
void listing(vector<string> list) {
int i = 0, size = list.size();
cout << "sorted: ";
for(auto item:list) {
i++;
cout << item << ((i < size)?", ":"");
}
cout << endl;
return;
}
//parse function
void parse(string input, vector<string> &tokens, string del)
{
tokens.clear();
int countDel =0;
for(int i = 0; i< input.length(); i++){
if(input[i] == del[0])
countDel++;
}
int tokenSize = countDel +1;
for(int i=0; i< tokenSize; i++){
int x= input.find(del[0]);
tokens.push_back(input.substr(0,x));
input = input.substr(x+1);
}
}
//tokensize function
int tokenSize(string input, string del)
{
int size;
int countDel =0;
for(int i = 0; i< input.length(); i++){
if(input[i] == del[0])
countDel++;
}
return size = countDel + 1;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.