Description
For this computer assignment, you are to write a C++ program to sort numbers using the
heapsort technique. Your program first builds a heap structure for the numbers. Then, it
retrieves these numbers from the heap in a certain order and prints them out on
stdout.
The source file assignment7.cc is partially implemented and contains the complete
implementation of the main function. It is available at
/home/turing/mhou/public/csci340spring2019. Add and implement the
following functions in this source file.
• void build_heap ( vector < int >& v, int heap_size,
bool (*compar)(int, int) ): This function constructs a heap with
heap_size elements in the vector v. Pay attention that elements start at
position 1 (position 0 is wasted and ignored) in the vector. compar is a function
pointer (predicate) to compare two integers. build_heap will invoke
heapify specified below.
• void heapify( vector < int >& v, int heap_size, int r, bool
(*compar)(int, int) ): This function “heapifies” a tree at the root position
r, assuming r’s two sub-trees are already heaps. heap_size specifies the size
of the whole heap contained by the vector (the heap starts at position 1 of the
vector). This function uses the function pointer compar to compare two
elements. This function can be implemented recursively.
• bool less_than ( int e1, int e2 ): This function compares two
integers and returns true if e1 is less than e2. Otherwise it returns false.
When this function is used as predicate in build_heap, a min heap will be
constructed.
• bool greater_than ( int e1, int e2 ): This function compares two
integers and returns true if e1 is greater than e2. Otherwise it returns
false. When this function is used as predicate in build_heap, a max heap will
be constructed.
• void heap_sort ( vector < int >& v, int heap_size,
bool (*compar)(int, int) ): This function implement the heap sort
algorithm. At beginning the vector v contains a heap. At the end of this
function, vector v contains sorted elements. Similar to build_heap, there is a
predicate in the parameter list to specify how to compare two elements. If
less_than is passed in as argument here, the results are in ascending order. If
greater_than is used, the results are in descending order. heap_sort will
invoke extract_heap specified below. You can use the STL algorithm
reverse if necessary.
Heaps and Heapsort
2
• int extract_heap ( vector < int >& v, int& heap_size, bool
(*compar)(int, int) ): This function extracts the root of the heap recorded
in v, fills the root with the last element of the current heap, updates
heap_size, “heapifies” at the root, and returns the old root value. This function
will invoke heapify specified above.
• void print_vector ( vector < int >& v, int pos, int size ):
This function displays size number of elements contained in vector v
starting at position pos. It shows 8 elements per line. Each item occupies 5
spaces.
Programming Notes:
• Please implement the algorithms to build the heap and sort by heapsort. Do not
invoke the STL algorithms make_heap or heap_sort. If you do, you will get 0
points for this assignment.
• Please pay extra attention that in this assignment vectors’ elements start at position 1
(instead of position 0) unless otherwise specified.
• Include any necessary headers and add necessary global constants.
• You are not allowed to use any I/O functions from the C library, such as scanf or
printf. Instead, use the I/O functions from the C++ library, such as cin or
cout.
• In the final version of your assignment, you are not supposed to change existing
code, including the main method, provided to you in the original source file
assginment7.cc.
• To compile the source file, execute “ g++ -Wall assignment7.cc –o
assignment7.exe”. This will create the executable file assignment7.exe. To
test your program, execute “./assignment7.exe &> assignment7.out”,
which will put the output (including any error messages) in file
assignment7.out. You can find the correct output of this program in file
assignment7.out in the directory shown in the last page.
• Add documentation to your source file.
• Prepare your Makefile so that the TA only needs to invoke the command “make” to
compile your source file and produce the executable file assignment7.exe. Make
sure you use exactly the same file names specified here, i.e. assignment7.cc and
assignment7.exe, in your Makefile. Otherwise your submission will get 0
points.
• When your program is ready, submit your source file assignment7.cc and
Makefile to your TA by following the Assignment Submission Instructions.
