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 << "\n ";

while(!line.empty()) {

ss << line.front();

line.pop();

}

level++;

ss << "\nL" << level+1 << ": ";

x = 1; j = 0;

}

}

ss << "\n\nHeap Array: ";

int heap_size = heap.size();

for(auto str: heap){
ss << str << ((heap_size <= 1) ? " " : ", ");

heap_size--;

}

ss << "\n\n";

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 << "\n=== HeapSort Test Menu ===\n"
<< " TRACE is " << (trace?"ON\n":"OFF\n")
<< " new build a new heap by bulk adding \n"
<< " a (,) delimited list \n"
<< " add to heap \n"
<< " clear entire heap \n"
<< " remove from heap \n"
<< " view heap \n"
<< " sort by dumping out all items \n"
<< " trace toggle on/off \n"
<< " help \n"
<< " quit \n";

}

//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:\n\t";

for(int i =0; i<arr.size(); i++) cout << arr[i] << (i<arr.size()-1?", ":"\n");
MaxHeap<string> aHeap(arr);

cout << aHeap.toString(); //print the heap
cout << "The above Tree and Array are raw data for display purpose. "
<< "\nUse command-new or command-add to build a HEAP.\n\n";

auto menu = []() {
cout << "\n=== HeapSort Test Menu ===\n"
<< " TRACE is " << (trace?"ON\n":"OFF\n")
<< " new build a new heap by bulk adding \n"
<< " a (,) delimited list \n"
<< " add to the heap \n"
<< " clear the entire heap \n"
<< " remove from the heap \n"
<< " view the entire heap \n"
<< " sort by dumping out all items \n"
<< " trace toggle on/off \n"
<< " help \n"
<< " quit \n";

};

menu(); //call the menu

int tSize;
string input, answer;
while(true){

cout << "\n>--- 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 << "\nInserting: ";
for(int i=0; i<tSize; i++)
cout << tokens[i] << (i<tSize-1?", ":"\n");
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 << " : \n";
}
}
else aHeap.build( tokens ) ;
tokens.clear();
cout << aHeap.toString();
}
  
else if ( answer == "sort" ) {
cout<<"\n ";
aHeap.sort();
}
else if ( answer == "view" || answer == "show" ) {
cout << aHeap.toString();
}
else if ( answer == "add" ) {
string in;
cout << "\nEnter a new item: ";
cin >> in;
cin.ignore(1000,'\n');
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.\n" ;
else cout << "Trace mode is NOT activated.\n" ;
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:

=== 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 :) 

Answer 1

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 << "\n ";
while(!line.empty()) {
ss << line.front();
line.pop();
}
level++;
ss << "\nL" << level+1 << ": ";
x = 1; j = 0;
}
}
ss << "\n\nHeap Array: ";
int heap_size = heap.size();
for(auto str: heap){
ss << str << ((heap_size <= 1) ? " " : ", ");
heap_size--;
}
ss << "\n\n";
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 << "\n=== HeapSort Test Menu ===\n"
<< " TRACE is " << (trace?"ON\n":"OFF\n")
<< " new build a new heap by bulk adding \n"
<< " a (,) delimited list \n"
<< " add to heap \n"
<< " clear entire heap \n"
<< " remove from heap \n"
<< " view heap \n"
<< " sort by dumping out all items \n"
<< " trace toggle on/off \n"
<< " help \n"
<< " quit \n";
}

//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:\n\t";
for(int i =0; i<arr.size(); i++) cout << arr[i] << (i<arr.size()-1?", ":"\n");
MaxHeap<string> aHeap(arr);
cout << aHeap.toString(); //print the heap
cout << "The above Tree and Array are raw data for display purpose. "
<< "\nUse command-new or command-add to build a HEAP.\n\n";
auto menu = []() {
cout << "\n=== HeapSort Test Menu ===\n"
<< " TRACE is " << (trace?"ON\n":"OFF\n")
<< " new build a new heap by bulk adding \n"
<< " a (,) delimited list \n"
<< " add to the heap \n"
<< " clear the entire heap \n"
<< " remove from the heap \n"
<< " view the entire heap \n"
<< " sort by dumping out all items \n"
<< " trace toggle on/off \n"
<< " help \n"
<< " quit \n";
};
menu(); //call the menu
int tSize;
string input, answer;
while(true){
cout << "\n>--- 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 << "\nInserting: ";
for(int i=0; i<tSize; i++)
cout << tokens[i] << (i<tSize-1?", ":"\n");
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 << " : \n";
}
}
else aHeap.build( tokens ) ;
tokens.clear();
cout << aHeap.toString();
}

else if ( answer == "sort" ) {
cout<<"\n ";
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 << "\nEnter a new item: ";
cin >> in;
cin.ignore(1000,'\n');
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.\n" ;
else cout << "Trace mode is NOT activated.\n" ;
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;
}