This lab is to help reinforce heap and priority queue implementations in C++. Specifically, the lab is to problem 2 on page 582 of the text. Note that you will need to implement a heap class (use a vector instead of a dynamic array) and then use the heap class to implement a priority queue. You need to construct a test program to help test the correctness of your code. You need to use heap.h and priority_queue.h.

heap.h

#ifndef _HEAP_H_

#define _HEAP_H_

#include

#include

// This class implements an unbounded max heap.

// class invariant: heap property is satisfied for a max heap

template

class heap

{

public:

heap();

// postcondition: empty heap has been created

unsigned int size() const;

// postcondition: number of elements in a heap has been returned

bool is_empty() const;

// postcondtion: returned whether the heap is empty

void insert (const T& item);

// postcondition: item has been added

void remove();

// precondition: heap is not empty

// postcondition: largest item has been removed from the heap

T max() const;

// precondition: heap is not empty

// postcondition: copy of largest element in the heap has been returned

T& max();

// precondition: heap is not empty

// postcondition: access to largest element in the heap has been returned

private:

std::vector v;

unsigned int max_child (unsigned int index) const;

// precondition: element at index has children

// postcondition: index of the larger child has been returned

// if there is only 1 child - index of that child has been returned

};

#include "heap.template"

#endif // _HEAP_H_

____________________________________________________________________

heap.cpp

#include "heap.h" // precondition: element at index has children // postcondition: index of the larger child has been returned // if there is only 1 child - index of that child has been returned template typename T> unsigned int heap::max_child (unsigned int index) const { unsigned int left_child(index*2+1); unsigned int right_child(index*2+2); assert(v.size() > left_child); if (v.size() > right_child) { //has two children if (v[left_child] > v[right_child]) { return left_child; } else  { return right_child; } } else  { //has only left child return left_child; } } // postcondition: empty heap has been created template typename T> heap::heap() : v() { } // postcondition: number of elements in a heap has been returned template typename T> unsigned int heap::size() const { return v.size(); } // postcondtion: returned whether the heap is empty template typename T> bool heap::is_empty() const { if (size() == 0) { return true; } return false; } // postcondition: item has been added template typename T> void heap::insert (const T& item) { v.push_back(item); //the class invariance unsigned int child_index = size()-1; unsigned int parent_index = (child_index-1)/2; if (parent_index return; } while (child_index > 0) { if (v[parent_index] else  { break; } } } // precondition: heap is not empty // postcondition: largest item has been removed from the heap template typename T> void heap::remove() { assert(!is_empty()); if (size() == 1) { v.erase(v.begin()); return; } v[0] = v[v.size()-1]; v.erase(v.begin()+v.size()-1); unsigned int parent_index = 0; unsigned int child_index = 0; while (size() > parent_index*2+1) { child_index = max_child(parent_index); if (v[child_index] > v[parent_index]) { T tmp = v[parent_index]; v[parent_index] = v[child_index]; v[child_index] = tmp; parent_index = child_index; } else  { break; } } } // precondition: heap is not empty // postcondition: copy of largest element in the heap has been returned template typename T> T heap::max() const { assert(!is_empty()); return v[0]; } // precondition: heap is not empty // postcondition: access to largest element in the heap has been returned template typename T> T& heap::max() { assert(!is_empty()); return v[0]; }

____________________________________________________________________

priority_queue.h

#ifndef _PRIORITY_QUEUE_H

#define _PRIORITY_QUEUE_H

#include "heap.h"

template

class priority_queue

{

public:

priority_queue();

// postcondition: empty priority_queue has been created

void pop();

// precondition: priority_queue is not emtpy

// postcondition: highest priority item has been removed

void push (const T& item);

// postcondition: item has been inserted

bool empty () const;

// postcondition: returned whether priority queue is empty

unsigned int size() const;

// postcondition: returned number of items in the priority queue

T top() const;

// precondition: priority queue is not empty

// postcondition: copy of highest priority item has been returned

private:

heap h;

};

#include "priority_queue.template"

#endif // _PRIORITY_QUEUE_H

____________________________________________________________________________________

Using a heap, implement the priority queue class from Section 8.4. The class should have a static constant member variable CAPACITY, which is the maximum size of the heap (as in the solution to Self-Test Exercise 2) and an ar ray, data, that contains the heap with the entries We also want to have FIFO behavior for entries with equal priority. To obtain this behavior, the class should have an extra private member variable that is an array, order, where order[i] contains the order in which data[i] was added to the queue. For ex ample, if entry[7] was the 33rd item added to the priority queue, then order [7] would be 33. When you are comparing two entries with equal priority use the order number to "break the tie" (so that if two entries have the same priority number, then the one with the earlier order number will come out of the priority queue first) Repeat Project 1, with no predefined limit on the size of the heap. Use a dynamic array Using a heap, implement the priority queue class from Section 8.4. The class should have a static constant member variable CAPACITY, which is the maximum size of the heap (as in the solution to Self-Test Exercise 2) and an ar ray, data, that contains the heap with the entries We also want to have FIFO behavior for entries with equal priority. To obtain this behavior, the class should have an extra private member variable that is an array, order, where order[i] contains the order in which data[i] was added to the queue. For ex ample, if entry[7] was the 33rd item added to the priority queue, then order [7] would be 33. When you are comparing two entries with equal priority use the order number to "break the tie" (so that if two entries have the same priority number, then the one with the earlier order number will come out of the priority queue first) Repeat Project 1, with no predefined limit on the size of the heap. Use a dynamic array