data structure lab 1
ahmeddxn7
Lab8_PriorityQueue.zipLab8_PriorityQueue/Heap.h
#ifndef HEAPTYPE_H #define HEAPTYPE_H template <class ItemType> void swap(ItemType& one, ItemType& two); // Assumes ItemType is either a built-in simple type or a class // with overloaded relational operators. template<class ItemType> struct HeapType { void ReheapDown(int root, int bottom); void ReheapUp(int root, int bottom); //Extra HeapSort function with a variation of ReheapDown that takes three parameters. void HeapSort(int numValues); void ReheapDown(ItemType elements[], int root, int bottom); ItemType* elements; // Array to be allocated dynamically }; template <class ItemType> void Swap(ItemType& one, ItemType& two) { ItemType temp; temp = one; one = two; two = temp; } template<class ItemType> void HeapType<ItemType>::ReheapUp(int root, int bottom) // Post: Heap property is restored. { int parent; if (bottom > root) { parent = (bottom-1) / 2; if (elements[parent] < elements[bottom]) { Swap(elements[parent], elements[bottom]); ReheapUp(root, parent); } } } template<class ItemType> void HeapType<ItemType>::ReheapDown(int root, int bottom) // Post: Heap property is restored. { int maxChild; int rightChild; int leftChild; leftChild = root*2+1; rightChild = root*2+2; if (leftChild <= bottom) { if (leftChild == bottom) maxChild = leftChild; else { if (elements[leftChild] <= elements[rightChild]) maxChild = rightChild; else maxChild = leftChild; } if (elements[root] < elements[maxChild]) { Swap(elements[root], elements[maxChild]); ReheapDown(maxChild, bottom); } } } template<class ItemType> void HeapType<ItemType>::HeapSort(int numValues) // Pre: Struct HeapType is available. // Post: The elements in the array values are sorted by key. { int index; // Convert the array of values into a heap. for (index = numValues/2 - 1; index >= 0; index--) ReheapDown(elements, index, numValues-1); // Sort the array. for (index = numValues-1; index >=1; index--) { Swap(elements[0], elements[index]); ReheapDown(elements, 0, index-1); } } template<class ItemType> void HeapType<ItemType>::ReheapDown(ItemType elements[], int root, int bottom) // Post: Heap property is restored. { int maxChild; int rightChild; int leftChild; leftChild = root*2+1; rightChild = root*2+2; if (leftChild <= bottom) { if (leftChild == bottom) maxChild = leftChild; else { if (elements[leftChild] <= elements[rightChild]) maxChild = rightChild; else maxChild = leftChild; } if (elements[root] < elements[maxChild]) { Swap(elements[root], elements[maxChild]); ReheapDown(elements, maxChild, bottom); } } } #endif
Lab8_PriorityQueue/PQDr.cpp
Lab8_PriorityQueue/PQDr.cpp
//Ivan Temesvari
//4/1/2019
//Lab 8 driver
#include
<
iostream
>
#include
<
fstream
>
typedef
int
ItemType
;
#include
"PQType.h"
using
namespace
std
;
int
main
()
{
//sample code for using a PQType
ItemType
item
;
PQType
<
int
>
queue
(
50
);
queue
.
Enqueue
(
5
);
queue
.
Enqueue
(
10
);
queue
.
Enqueue
(
4
);
cout
<<
queue
<<
endl
;
return
0
;
}
Lab8_PriorityQueue/PQType.h
#ifndef PQTYPE_H #define PQTYPE_H // Definition of class PQType, which represents the Priority Queue ADT class FullPQ{}; class EmptyPQ{}; #include <iostream> #include "Heap.h" using namespace std; #define MAX_ITEMS 10 template<class ItemType> class PQType { public: PQType(); //default constructor PQType(int); // parameterized class constructor ~PQType(); // class destructor PQType operator=(const PQType& rhs); void MakeEmpty(); // Function: Initializes the queue to an empty state. // Post: Queue is empty. bool IsEmpty() const; // Function: Determines whether the queue is empty. // Post: Function value = (queue is empty) bool IsFull() const; // Function: Determines whether the queue is full. // Post: Function value = (queue is full) void Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue. // Post: if (the priority queue is full) exception FullPQ is thrown; // else newItem is in the queue. void Dequeue(ItemType& item); // Function: Removes element with highest priority from the queue // and returns it in item. // Post: If (the priority queue is empty) exception EmptyPQ is thrown; // else highest priority element has been removed from queue. // item is a copy of removed element. template <class ItemPQ> friend ostream& operator<<(ostream& out, const PQType<ItemPQ>& pq); private: int length; HeapType<ItemType> items; int maxItems; }; template<class ItemType> PQType<ItemType>::PQType(){ maxItems = MAX_ITEMS; items.elements = new ItemType[maxItems]; length = 0; } template<class ItemType> PQType<ItemType>::PQType(int max) { maxItems = max; items.elements = new ItemType[maxItems]; length = 0; } template<class ItemType> PQType<ItemType> PQType<ItemType>::operator=(const PQType<ItemType>& rhs){ //assignment operator= if(this == &rhs){ return *this; } else{ //delete old contents of this delete [] items.elements; length = 0; maxItems = rhs.maxItems; items.elements = new ItemType[rhs.maxItems]; //copy new contents over to this from rhs int count = 0; while(count < rhs.length){ items.elements[count] = rhs.items.elements[count]; count++; } } return *this; } template<class ItemType> void PQType<ItemType>::MakeEmpty() { length = 0; } template<class ItemType> PQType<ItemType>::~PQType() { delete [] items.elements; } template<class ItemType> void PQType<ItemType>::Dequeue(ItemType& item) // Post: element with highest priority has been removed // from the queue; a copy is returned in item. { if (length == 0) throw EmptyPQ(); else { item = items.elements[0]; items.elements[0] = items.elements[length-1]; length--; items.ReheapDown(0, length-1); } } template<class ItemType> void PQType<ItemType>::Enqueue(ItemType newItem) // Post: newItem is in the queue. { if (length == maxItems) throw FullPQ(); else { length++; items.elements[length-1] = newItem; items.ReheapUp(0, length-1); } } template<class ItemType> bool PQType<ItemType>::IsFull() const // Post: Returns true if the queue is full; false, otherwise. { return length == maxItems; } template<class ItemType> bool PQType<ItemType>::IsEmpty() const // Post: Returns true if the queue is empty; false, otherwise. { return length == 0; } template <class ItemPQ> ostream& operator<<(ostream& out, const PQType<ItemPQ>& pq){ for(int i = 0; i < pq.length; i++){ out << pq.items.elements[i] << endl; } return out; } #endif
