How to add a new heap implementation

The steps needed to add a new heap implementation are

• Add a directory to hold your source code.
• Add rules to the makefile to build the driver programs with the new implementation. The best thing to do is to use the existing rules as a model.
• Write your program.

If you are writing a heap as a priority queue, the file basic/heapsort.cc can be used to turn it into a heapsort for testing purposes. Otherwise if you are writing a heapsort directly you can use it as a model for the interface to the driver programs. The driver programs expects that heap implementations are named heap.cc while heapsort implementations must be named heapsort.cc. A heap must be implemented as a class template named heap taking two parameters. The first parameter specifies the element type, while the second parameter specifies the ordering relation.

A heapsort implementation is similar except that it must be named HeapSort.

• Driver programs
  • build_driver.cc
  • sort_driver.cc
  • count_driver.cc
  • debug_driver.cc
  • pq_driver.cc
• Useful scripts
  • sortdrive.sh
  • pqdrive.sh
  • speedup.sh