An airline company uses the formula shown below to determine the priority of the passengers on the waiting list for overbooked flights.

Priority number = A / 1000 + B C Where

A is the customers total mileage in the past year B is the customers number of years in the flier program C is the sequence number representing the customers arrival position when the flight was booked (the first customers sequence number is 1, second in the file is 2, and so on).

Build the heap based on the serial number: serial number = priority * 100 + (100 C). Given a file with overbooked customers, overbooked.txt, write a program that reads the file and determines each customers priority number and prints a list of waiting customers (name and their priority and serial numbers) in priority sequence, including the number of customers. A line in the input file contains the number of years in the frequent flier program, total mileage in the past year, and the name of the customer as shown below:

 5 53000 Robert Hill 

Requirements:

Customer class

Build heap from file

Print heap as an indented tree (Right Root-Left traversal)

(show the serial number and the name of the customer)

Print customers in priority sequence

(show year, mileage, and name)

Heap class (ADT )

main(), and other functions

---->This is Heap.h:

#ifndef HEAP_H_ #define HEAP_H_

template class Heap { private: ItemType* heapAry; int arySize; int count; //function pointer compare : 0 means equal, 1 means left > right, -1 means left < right void _reHeapUp(int lastndx, int compare(ItemType &, ItemType &)); void _reHeapDown(int rootndx, int compare(ItemType &, ItemType &)); int _findParent(int index) { return (index <= 0) ? (-1) : (index - 1) / 2; } int _findLeftChild(int index) { return (2 * index + 1 > count) ? (-1) : ( 2 * index + 1); } int _findRightChild(int index) { return (2 * index + 2 > count) ? (-1) : ( 2 * index + 2); }

public: Heap() { count = 0; arySize = 128; heapAry = new ItemType[arySize]; } Heap(int n) { count = 0; arySize = n; heapAry = new ItemType[arySize]; } ~Heap(){ delete [] heapAry; }

int getCount() const { return count; } bool isEmpty() const { return count == 0; } bool isFull() const { return count == arySize; } bool insertHeap( ItemType &itemIn, int compare(ItemType &, ItemType &) ); bool deleteHeap( ItemType &itemOut, int compare(ItemType &, ItemType &) );

};

/**~*~* The private member function _reHeapUp rearranges the heap after insert by moving the last item up to the correct location in the heap *~**/ template void Heap::_reHeapUp(int lastndx, int compare(ItemType &, ItemType &)) { if(lastndx) { int parent = findParent(lastndx); // finish writing this recursive function } }

/**~*~* The private member function _reHeapDown rearranges the heap after delete by moving the data in the root down to the correct location in the heap *~**/ template void Heap::_reHeapDown(int rootdex, int compare(ItemType &, ItemType &)) { int left = findLeftChild(rootdex); // finish writing this recursive function

}

/**~*~* The public member function insertHeap inserts a new item into a heap. It calls _reheapUp. *~**/ template bool Heap::insertHeap(ItemType& newItem, int compare(ItemType &, ItemType &)) { // finish writing this function return true; }

/**~*~* The public member function deleteHeap deletes the root of the heap and passes back the root's data. It calls _reheapDown. *~**/ template bool Heap::deleteHeap(ItemType& returnItem, int compare(ItemType &, ItemType &)) { // finish writing this function return true; }

#endif