Practical Week 8
Objectives: To understand more about heaps and heapsort.
-
Using heap.h and heap.cc and item.h implement
and test heapSort. See simple-minded version from lectures or example in Carrano.
If links to header files don't work (they do work sometimes) then just use the files that you downloaded from carrano website. Or cut and paste the files below.
Submit this program via web-CT.
- Debug the program trypq.cc which implements a priority queue of Item (where Item is defined as a class). Experiment with changing the priority queue to handle smallest value as top priority.
heap.h
// *********************************************************
// Header file Heap.h for the ADT heap.
// modified from Carrano
// *********************************************************
#include
using namespace std;
#include "Item.h"
#ifndef HEAPFILE
#define HEAPFILE 1
typedef Item HeapItemType;
const int MAX_HEAP = 50;
class Heap
{
public:
Heap(); // default constructor
virtual bool heapIsEmpty() const;
// Determines whether a heap is empty.
// Precondition: None.
// Postcondition: Returns true if the heap is empty;
// otherwise returns false.
virtual void heapInsert(const HeapItemType& newItem);
// Inserts an item into a heap.
// Precondition: newItem is the item to be inserted.
// Postcondition: If the heap was not full, newItem is
// in its proper position
virtual void heapDelete();
// Deletes the item in the root of a heap.
// This item has the smallest search key in the heap.
// Precondition: None.
// Postcondition: If the heap was not empty,
// the item is deleted from the
// heap; otherwise, heap is unchanged
virtual HeapItemType heapRoot();
// precondition: heap is not empty
// postcondition: returns value at root
virtual int heapSize();
// postcondition: returns size of heap
protected:
void heapRebuild(int root);
// Converts the semiheap rooted at index root
// into a heap.
private:
HeapItemType items[MAX_HEAP]; // array of heap items
int size; // number of heap items
}; // end class
// End of header file.
#endif
item.h
#include
#include
#include
using namespace std;
class Item {
private:
int key;
char elem;
public:
Item(int k, char e): key(k), elem(e){};
char element() { return elem; }
int getKey() const {return key;}
char getElement()const { return elem; }
void setKey(int k) { key = k; }
void setElement( char e) { elem = e; }
bool operator< (const Item& n) const {
return key < n.key ;
}
};