Assignment 6 Heap Sort

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

Submit

MaxHeap.h,

testMaxHeap.cpp and

test run validation (use similar scenarios to the test run sample)