Purpose

The Heapsorts running time is O(n*log n). Like insertion sort, but unlike merge sort, heapsort sorts in place. In this assignment we are going to build a user interface with the provided display helper method to allow the user viewing the steps of building a heap and steps of sorting the data from a heap.

Description

Here are major steps in utilizing this heap sort assignment:

To allow user to enter a delimited string list.

To create a max-heap from a user input (unordered) list.

To Heap Sort by successively remove the root of the heap and place the item on the left of the sorted list.

To utilize the displayHeap() helper, so the user may see the Heap in both array and tree view.

The Heap and the user list should be kept in separate variables. The starter kit uses vector of string for both variables.

Both Heap creation and Heap sorting need to utilize the heapify function.

The displayHeap() helper is more than display the Heap array, but the entire array to help us to see the heap sort in action.

Implementation

User Interface

Implement the menu as shown below (modifying from the menu driver from AS5 starter):

All the user interface shall look similar to the single character command menu that we have been using before except the command is word based.

Built-in displayHeap() Helper

This displayHeap() helper is a ready program for you to use. The purpose of this helper is to enhance your learning through the visualization of the changing heap. You don't have to know how the displayHeap() works nor making changes to it. However, if you are really interested in this work, you are welcome to share your idea with me.

The heapsort_starter.cpp starts up with the TRACE off, you will need to turn on the TRACE to see the output of the displayHeap(). See the execution trace and you may notice certain nodes are not connected to the tree, those nodes are not part of the heap.

Content of the starter

Instead of the array, we use the STL vector as an array. Inside the MaxHeap_starter.cpp, this test driver/application upgraded to encapsulate all the Max Heap related functions: displayHeap(), parser(), build(), toString(), ...etc.

* If you are trying to build the MaxHeap class from scratch, you should define the class interface than implement the feature set, step by step.

displayHeap() helper

This helper function is re-designed to a MaxHeap::toString() (Links to an external site.)Links to an external site. class method of the MaxHeap class.

Sample Execution A screen capture is provided below. In order to align the graph display format on your console, you will need to set the font to mono space, such as courier or any font name ending with MS. Your finished program should work the same way as the provided (PC) executable :

WHAT YOU ARE TO BUILD:

1. build a MaxHeap class

Fill the blank in the MaxHeap_starter.h:

bubbleUp method

trickleDown method

2. complete the test application (all the menu commands)

Fill the blank in the as6_testMaxHeap_starter.cpp

command-sort (Heap Sort) in the menu.

Sample Test Execution A screen capture is provided below. In order to align the graph display format on your console, you will need to set the font to mono space, such as courier or any font name ending with MS. Your finished program should be able to generate the sample test operational result as below:

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

Assign6.cpp

#include

#include

#include "MaxHeap_starter.h"

using namespace std;

bool trace = false; // Not good, but easier this way.

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

}

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

MaxHeap aHeap(arr);

cout << aHeap.toString();

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();

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

cout << tokens[i] << (i

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" ) {

//

// fill the blank 3

//

}

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;

}

void listing(vector list) {

int i = 0, size = list.size();

cout << "sorted: ";

for(auto item:list) {

i++;

cout << item << ((i < size)?", ":"");

}

cout << endl;

return;

}

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);

}

}

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;

}

maxheap.h

#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 add(T newValue);

bool replace(vector array) {

heap.clear();

heap = array;

};

bool build(vectorarray) {

heap = array;

Heapify();

};

string toString();

};

template // old blank 1

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) {

//

// fill the blank 2

//

}

template

void MaxHeap::remove(){

int length = heap.size();

if(length == 0) return;

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

heap.pop_back();

trickleDown(0);

}

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();

}