Need help with the trickle down

This is the maxheap.h

#ifndef MAXHEAP_H_INCLUDED #define MAXHEAP_H_INCLUDED

#include #include #include #include #include // pow()

using namespace std;

#define PARENT(i) ((i-1) / 2) #define LINE_WIDTH 60.0

template

class MaxHeap{ // private:

vector 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 &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 array) { heap.clear(); heap = array; }; bool build(vectorarray) { heap = array; Heapify(); };

string toString();

};

template // old blank 1 //bubble up class void MaxHeap::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

void MaxHeap::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

void MaxHeap::remove(){

int length = heap.size();

if(length == 0) return;

heap[0] = heap[length - 1];

heap.pop_back();

trickleDown(0);

}

template //sort function void MaxHeap::sort(){

int length = heap.size();

if(length == 0) return;

heap[0] = heap[length - 1];

for (int i=0;i

}

}

template

void MaxHeap::add(T newValue) {

int length = heap.size();

heap.push_back(newValue);

bubbleUp(length);

}

template

string MaxHeap::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 line;

ss << "L1: "; // the left margin

print_pos[0] = 0;

dash = '-';

for(i=0,j=1; i

pos = print_pos[((i-1) / 2)]

+ ((i%2?-1:1)*(LINE_WIDTH/(pow(2,level+1))));

for (k=0; 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 #include #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 &tokens, string del); int tokenSize(string input, string del); void listing(vector list);

int main( ) {

string del = ","; vector sorted; vector 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: \t";

for(int i =0; i 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 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=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 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 &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:

=== HeapSort Test Menu === TRACE is 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 >--- Enter your choice -> trace Trace mode is activated. >--- Enter your choice -> new New list: 4,5,6,r,t,y,2,z,9,a List Size: 10 Inserting: 4, 5, 6, r, t, y, 2, z, 9, a L1: 4 | L2: 5-----------------------------6 | | L3: r--------------t y--------------2 | | | | L4: z------9 a-------- Heap Array: 4, 5, 6, r, t, y, 2, z, 9, a check item 4 : L1: 4 | L2: 5-----------------------------6 | | L3: r--------------a y--------------2 | | | | L4: z------9 t-------- Heap Array: 4, 5, 6, r, a, y, 2, z, 9, t check item 3 : L1: 4 | L2: 5-----------------------------6 | | L3: 9--------------a y--------------2 | | | | L4: z------r t-------- Heap Array: 4, 5, 6, 9, a, y, 2, z, r, t check item 2 : L1: 4 | L2: 5-----------------------------2 | | L3: 9--------------a y--------------6 | | | | L4: z------r t-------- Heap Array: 4, 5, 2, 9, a, y, 6, z, r, t check item 1 : L1: 4 | L2: 5-----------------------------2 | | L3: 9--------------a y--------------6 | | | | L4: z------r t-------- Heap Array: 4, 5, 2, 9, a, y, 6, z, r, t check item 0 : L1: 2 | L2: 5-----------------------------4 | | L3: 9--------------a y--------------6 | | | | L4: z------r t-------- Heap Array: 2, 5, 4, 9, a, y, 6, z, r, t 

Need an output like this:

=== HeapSort Test Menu === TRACE is 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 teh entire heap sort by dumping out all items trace toggle on/off help quit >--- Enter your choice -> trace Trace mode is activated. >--- Enter your choice -> new New list: 4,5,6,r,t,y,2,z,9,a List Size: 10 Inserting: 4, 5, 6, r, t, y, 2, z, 9, a L1: 4 | L2: 5-----------------------------6 | | L3: r--------------t y--------------2 | | | | L4: z------9 a-------- Heap Array: 4, 5, 6, r, t, y, 2, z, 9, a check item 4 : L1: 4 | L2: 5-----------------------------6 | | L3: r--------------t y--------------2 | | | | L4: z------9 a-------- Heap Array: 4, 5, 6, r, t, y, 2, z, 9, a check item 3 : L1: 4 | L2: 5-----------------------------6 | | L3: z--------------t y--------------2 | | | | L4: r------9 a-------- Heap Array: 4, 5, 6, z, t, y, 2, r, 9, a check item 2 : L1: 4 | L2: 5-----------------------------y | | L3: z--------------t 6--------------2 | | | | L4: r------9 a-------- Heap Array: 4, 5, y, z, t, 6, 2, r, 9, a check item 1 : L1: 4 | L2: z-----------------------------y | | L3: r--------------t 6--------------2 | | | | L4: 5------9 a-------- Heap Array: 4, z, y, r, t, 6, 2, 5, 9, a check item 0 : L1: z | L2: t-----------------------------y | | L3: r--------------a 6--------------2 | | | | L4: 5------9 4-------- Heap Array: z, t, y, r, a, 6, 2, 5, 9, 4 >--- Enter your choice -> sort L1: z | L2: t-----------------------------y | | L3: r--------------a 6--------------2 | | | | L4: 5------9 4-------- Heap Array: z, t, y, r, a, 6, 2, 5, 9, 4 sorted: z L1: y | L2: t-----------------------------6 | | L3: r--------------a 4--------------2 | | | | L4: 5------9 Heap Array: y, t, 6, r, a, 4, 2, 5, 9 sorted: y, z L1: t | L2: r-----------------------------6 | | L3: 9--------------a 4--------------2 | | | | L4: 5-- Heap Array: t, r, 6, 9, a, 4, 2, 5 sorted: t, y, z L1: r | L2: a-----------------------------6 | | L3: 9--------------5 4--------------2 | | | | L4: Heap Array: r, a, 6, 9, 5, 4, 2 sorted: r, t, y, z L1: a | L2: 9-----------------------------6 | | L3: 2--------------5 4--------------- Heap Array: a, 9, 6, 2, 5, 4 sorted: a, r, t, y, z L1: 9 | L2: 5-----------------------------6 | | L3: 2--------------4 Heap Array: 9, 5, 6, 2, 4 sorted: 9, a, r, t, y, z L1: 6 | L2: 5-----------------------------4 | | L3: 2------ Heap Array: 6, 5, 4, 2 sorted: 6, 9, a, r, t, y, z L1: 5 | L2: 2-----------------------------4 | | L3: Heap Array: 5, 2, 4 sorted: 5, 6, 9, a, r, t, y, z L1: 4 | L2: 2-------------- Heap Array: 4, 2 sorted: 4, 5, 6, 9, a, r, t, y, z L1: 2 | L2: Heap Array: 2 sorted: 2, 4, 5, 6, 9, a, r, t, y, z sorted: 2, 4, 5, 6, 9, a, r, t, y, z >--- Enter your choice -> >--- Enter your choice -> quit GOOD BYE :)