Reheapdown

Lab8_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

Applied Sciences

Architecture and Design

Biology

Business & Finance

Chemistry

Computer Science

Geography

Geology

Education

Engineering

English

Environmental science

Spanish

Government

History

Human Resource Management

Information Systems

Law

Literature

Mathematics

Nursing

Physics

Political Science

Psychology

Reading

Science

Social Science

Home

Blog

Archive

Contact

google+twitterfacebook

Copyright © 2019 HomeworkMarket.com