// BinaryHeap_HW4.h // KV, May 2018, after Weiss, Data Structures textbook // KV
ID: 3903201 • Letter: #
Question
// BinaryHeap_HW4.h // KV, May 2018, after Weiss, Data Structures textbook// KV: version for HW4; counts comps for insert and deleteMin;
#ifndef BINARYHEAP_H_ #define BINARYHEAP_H_
#include <cassert> #include "Vector.h" using namespace std;
extern int CLUMSY_COUNT;
template <typename C> class BinaryHeap { public: BinaryHeap() : heap(100), currentSize(0) {} BinaryHeap(int capacity) : heap(capacity), currentSize(0) {} BinaryHeap(const Vector<C>&); bool isEmpty() const { return currentSize == 0; } int size() const { return currentSize; } const C & findMin() const { return heap[1]; } void insert(const C &); void insert(C &&); void deleteMin(); void deleteMin(C &); void makeEmpty() { while (!heap.isEmpty()) heap.pop_back(); currentSize = 0; } void printHeap() const { printHeap(1,0); } private: int currentSize; Vector<C> heap; void buildHeap() { for (int i = currentSize/2; i > 0; i--) percolateDown(i); } void percolateDown(int); void printHeap(int,int) const; };
template <typename C> BinaryHeap<C>::BinaryHeap(const Vector<C>& items) : heap(items.size() + 10), currentSize(items.size()) { for (int i = 0; i < items.size(); i++) heap[i + 1] = items[i]; buildHeap(); }
template <typename C> void BinaryHeap<C>::insert(const C& x) { if (currentSize == heap.size()-1) heap.resize(heap.size()*2); int hole = ++currentSize; C copy = x; heap[0] = std::move(copy); for (; x < heap[hole/2]; hole /= 2) { CLUMSY_COUNT++; heap[hole] = std::move(heap[hole/2]); } heap[hole] = std::move(heap[0]); }
template <typename C> void BinaryHeap<C>::insert(C&& x) { if (currentSize == heap.size()-1) heap.resize(heap.size()*2); int hole = ++currentSize; C copy = x; heap[0] = std::move(copy); for (; x < heap[hole/2]; hole /= 2) heap[hole] = std::move(heap[hole/2]); heap[hole] = std::move(heap[0]); }
template <typename C> void BinaryHeap<C>::deleteMin() { assert(!isEmpty()); heap[1] = std::move(heap[currentSize--]); percolateDown(1); }
template <typename C> void BinaryHeap<C>::deleteMin(C & minItem) { assert(!isEmpty()); minItem = std::move(heap[1]); heap[1] = std::move(heap[currentSize--]); percolateDown(1); }
template <typename C> void BinaryHeap<C>::percolateDown(int hole) { int child; C tmp = std::move(heap[hole]); for (; hole * 2 <= currentSize; hole = child) { CLUMSY_COUNT++; child = hole * 2; if (child != currentSize && heap[child + 1] < heap[child]) child++; if (heap[child] < tmp) heap[hole] = std::move(heap[child]); else break; } heap[hole] = std::move(tmp); }
template <typename C> void BinaryHeap<C>::printHeap(int index, int offset) const { if (index > currentSize) return; for (int i = 1; i <= offset; i++) cout << ".."; cout << heap[index] << endl; printHeap(2*index, offset + 1); printHeap(2*index+1, offset + 1); return; }
#endif ——————————————————————// BST_HW4.h // KV May 2018, based on // KV replaced exceptions with assert statements;
// version of BST_HW3 that keeps track of insertion and // iteratation costs;
#ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H
//#include "dsexceptions.h" #include <cassert> #include <algorithm> #include <queue> #include <iostream>
using namespace std;
int CLUMSY_COUNT = 0;
template <typename C> class BinarySearchTree { private: struct BinaryNode { C element; BinaryNode *left; BinaryNode *right; BinaryNode *parent; BinaryNode(const C & elem, BinaryNode *lt, BinaryNode *rt, BinaryNode *par) : element(elem), left(lt), right(rt), parent(par) {} }; public: //struct BinaryNode; class iterator {public: iterator() : current{nullptr} {} iterator(BinaryNode * t) : current(t) {} C & operator *() const { return current->element; } bool operator ==(iterator other) const { return current == other.current; } bool operator != (iterator other) const { return current != other.current; } iterator & operator ++() { if (is_root(current)) current = leftmost(current->right); else if (is_left_child(current)) { if (current->left == nullptr && current->right == nullptr) { current = current->parent; CLUMSY_COUNT++; } else if (current->right != nullptr) current = leftmost(current->right); else { //; // should not happen current = current->parent; // NEW!! CLUMSY_COUNT++; } } else if (is_right_child(current)) { if (current->right != nullptr) current = leftmost(current->right);else current = follow_parent_until_leftchild(current); } return *this; } iterator & operator++(int) { iterator old(*this); ++(*this); return old; } protected: BinaryNode * current; /* bool is_right_child(BinaryNode * t) { return (t != nullptr && t->parent == nullptr); } */ bool is_root(BinaryNode *t) { return (t != nullptr && t->parent == nullptr); } bool is_left_child(BinaryNode *t) { assert(t != nullptr); if (t->parent != nullptr && t->parent->left == t) return true; else return false; } bool is_right_child(BinaryNode *t) { assert(t != nullptr); if (t->parent != nullptr && t->parent->right == t) return true; else return false; } BinaryNode * leftmost(BinaryNode *t) { if (t == nullptr) return nullptr; CLUMSY_COUNT++; if (t->left == nullptr) return t; return leftmost(t->left); } BinaryNode * follow_parent_until_leftchild(BinaryNode *t) { if (is_root(t)) return nullptr; CLUMSY_COUNT++; if (is_left_child(t)) return t->parent; return follow_parent_until_leftchild(t->parent); } friend class BinarySearchTree<C>; }; public: BinarySearchTree( ) : root{ nullptr } { } BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr } { root = clone( rhs.root); } BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root } { rhs.root = nullptr; } ~BinarySearchTree( ) { makeEmpty( ); } BinarySearchTree & operator=( const BinarySearchTree & rhs ) { BinarySearchTree copy = rhs; std::swap( *this, copy ); return *this; } BinarySearchTree & operator=( BinarySearchTree && rhs ) { std::swap( root, rhs.root ); return *this; } const C & findMin( ) const { assert(!isEmpty()); return findMin( root )->element; } const C & findMax( ) const { assert(!isEmpty()); return findMax( root )->element; } bool contains( const C & x ) const { return contains( x, root ); } bool isEmpty( ) const { return root == nullptr; } void printTree( ostream & out = cout ) const { if( isEmpty( ) ) out << "Empty tree" << endl; else printTree( root, out ); } void printInternal() { printInternal(root,0); } void makeEmpty( ) { makeEmpty( root ); } iterator insert( const C & x ) { return insert( x, root, root); } iterator insert( C && x ) { return insert( std::move( x ), root, root); } void remove( const C & x ) { remove( x, root ); } iterator begin() const { BinaryNode *t = root; while (t->left != nullptr) t = t->left; iterator beg(t); return beg; } iterator end() const { iterator theend(nullptr); return theend; } int size() const { if (root == nullptr) return 0; return 1 + size(root->left) + size(root->right); } private: BinaryNode *root; iterator insert( const C & x, BinaryNode * & t, BinaryNode * & par ) { if( t == nullptr ) { t = new BinaryNode{ x, nullptr, nullptr, par }; return iterator(t); } else if( x < t->element ) { CLUMSY_COUNT++; return insert( x, t->left, t ); } else if( t->element < x ) { CLUMSY_COUNT++; return insert( x, t->right, t ); } else return iterator(t); // Duplicate; do nothing } iterator insert( C && x, BinaryNode * & t, BinaryNode * & par ) { if( t == nullptr ) { t = new BinaryNode{ std::move( x ), nullptr, nullptr, par }; return iterator(t); } else if( x < t->element ) return insert( std::move( x ), t->left, t ); else if( t->element < x ) return insert( std::move( x ), t->right, t ); else return iterator(t); // Duplicate; do nothing } void remove( const C & x, BinaryNode * & t ) { if( t == nullptr ) return; // Item not found; do nothing if( x < t->element ) remove( x, t->left ); else if( t->element < x ) remove( x, t->right ); else if( t->left != nullptr && t->right != nullptr ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else{ BinaryNode *oldNode = t; if (t->left != nullptr) { t->left->parent = t->parent; t = t->left; } else { if (t->right != 0) t->right->parent = t->parent; t = t->right; } delete oldNode; } } BinaryNode * findMin( BinaryNode *t ) const { if( t == nullptr ) return nullptr; if( t->left == nullptr ) return t; return findMin( t->left ); } BinaryNode * findMax( BinaryNode *t ) const { if( t != nullptr ) while( t->right != nullptr ) t = t->right; return t; } bool contains( const C & x, BinaryNode *t ) const { if( t == nullptr ) return false; else if( x < t->element ) return contains( x, t->left ); else if( t->element < x ) return contains( x, t->right ); else return true; // Match } void makeEmpty( BinaryNode * & t ) { if( t != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; } void printTree( BinaryNode *t, ostream & out ) const { if( t != nullptr ) { printTree( t->left, out );out << t->element << endl; printTree( t->right, out ); } } void printInternal(BinaryNode* t, int offset) { for(int i = 1; i <= offset; i++) cout << ".."; if (t == nullptr) { cout << "#" << endl; return; } cout << t->element << endl; printInternal(t->left, offset + 1); printInternal(t->right, offset + 1); } BinaryNode * clone1(BinaryNode *t) const { if (t == nullptr) return nullptr; else return new BinaryNode(t->element, clone1(t->left), clone1(t->right), nullptr); } void put_parents(BinaryNode * t, BinaryNode * par) const { if (t == nullptr) return; t->parent = par; if (t->left != nullptr) put_parents(t->left, t); if (t->right != nullptr) put_parents(t->right, t); } BinaryNode * clone(BinaryNode *t) const { BinaryNode * theclone = clone1(t); put_parents(theclone, nullptr); return theclone; } int size(BinaryNode* t) const { if (t == nullptr) return 0; return 1 + size(t->left) + size(t->right); } }; #endif
// Random.h // KV, June 2018
// some random number generating utilities
#ifndef RANDOM_H_ #define RANDOM_H_
#include <iostream> #include <cstdlib> #include <ctime> #include <vector> #include <set>
using namespace std;
template <typename Cont> void rand_permute(Cont&);
void rand_seed() { int seed = static_cast<int>(time(0)); srand(seed); }
int rand_int(int a, int b) { return a + rand() % (b - a + 1); }
vector<int> rand_int_vector(int k, int a, int b) { set<int> set_of_k; vector<int> rvec; while (set_of_k.size() < k) { int rv = rand_int(a,b); set_of_k.insert(rv); } // will produce vector without duplicate values; set<int>::iterator itr = set_of_k.begin(); for (; itr != set_of_k.end(); ++itr) rvec.push_back(*itr); rand_permute(rvec); return rvec; }
template <typename Cont> void rand_permute(Cont& vals) { for (int i = 1; i <= vals.size()*3; i++) { int r1 = rand_int(0,vals.size()-1); int r2 = rand_int(0,vals.size()-1); typename Cont::iterator itr1 = vals.begin(); typename Cont::iterator itr2 = vals.begin(); for (int i = 1; i <= r1; i++) ++itr1; for (int i = 2; i <= r2; i++) ++itr2; std::swap(*itr1,*itr2); } return; }
#endif
// THSort_HW4.cpp // comparing the performance of TreeSort vs. HeapSort #include <iostream> #include <vector> #include <cmath> #include <cassert> #include "Random.h" #include "TreeSortHeapSort.h" using namespace std; int main() { vector<int> tosort1; vector<int> comps1; vector<int> comps2; int sum1; int sum2; int numdata = 25; rand_seed(); for (numdata = 10; numdata <= 50; numdata+=5) { sum1 = 0; sum2 = 0; for (int i = 1; i <= 25; i++) { tosort1 = rand_int_vector(numdata,1,1000); vector<int> tosort2(tosort1); int k1,k2; TreeSort(tosort1,k1); assert(tosort1.size() == numdata); HeapSort(tosort2,k2); assert(tosort2.size() == numdata); comps1.push_back(k1); comps2.push_back(k2); sum1 += k1; sum2 += k2; cout << endl; double nlogn = numdata* log10(numdata)/log10(2); int nn = numdata * numdata; double avg1 = (double)sum1 / 25; double avg2 = (double)sum2 / 25; cout << numdata << ", " << (int)avg1 << ", " << (int)avg2 << ", " << (int)nlogn << ", " << nn << endl; } } return 0; }
// BinaryHeap_HW4.h // KV, May 2018, after Weiss, Data Structures textbook
// KV: version for HW4; counts comps for insert and deleteMin;
#ifndef BINARYHEAP_H_ #define BINARYHEAP_H_
#include <cassert> #include "Vector.h" using namespace std;
extern int CLUMSY_COUNT;
template <typename C> class BinaryHeap { public: BinaryHeap() : heap(100), currentSize(0) {} BinaryHeap(int capacity) : heap(capacity), currentSize(0) {} BinaryHeap(const Vector<C>&); bool isEmpty() const { return currentSize == 0; } int size() const { return currentSize; } const C & findMin() const { return heap[1]; } void insert(const C &); void insert(C &&); void deleteMin(); void deleteMin(C &); void makeEmpty() { while (!heap.isEmpty()) heap.pop_back(); currentSize = 0; } void printHeap() const { printHeap(1,0); } private: int currentSize; Vector<C> heap; void buildHeap() { for (int i = currentSize/2; i > 0; i--) percolateDown(i); } void percolateDown(int); void printHeap(int,int) const; };
template <typename C> BinaryHeap<C>::BinaryHeap(const Vector<C>& items) : heap(items.size() + 10), currentSize(items.size()) { for (int i = 0; i < items.size(); i++) heap[i + 1] = items[i]; buildHeap(); }
template <typename C> void BinaryHeap<C>::insert(const C& x) { if (currentSize == heap.size()-1) heap.resize(heap.size()*2); int hole = ++currentSize; C copy = x; heap[0] = std::move(copy); for (; x < heap[hole/2]; hole /= 2) { CLUMSY_COUNT++; heap[hole] = std::move(heap[hole/2]); } heap[hole] = std::move(heap[0]); }
template <typename C> void BinaryHeap<C>::insert(C&& x) { if (currentSize == heap.size()-1) heap.resize(heap.size()*2); int hole = ++currentSize; C copy = x; heap[0] = std::move(copy); for (; x < heap[hole/2]; hole /= 2) heap[hole] = std::move(heap[hole/2]); heap[hole] = std::move(heap[0]); }
template <typename C> void BinaryHeap<C>::deleteMin() { assert(!isEmpty()); heap[1] = std::move(heap[currentSize--]); percolateDown(1); }
template <typename C> void BinaryHeap<C>::deleteMin(C & minItem) { assert(!isEmpty()); minItem = std::move(heap[1]); heap[1] = std::move(heap[currentSize--]); percolateDown(1); }
template <typename C> void BinaryHeap<C>::percolateDown(int hole) { int child; C tmp = std::move(heap[hole]); for (; hole * 2 <= currentSize; hole = child) { CLUMSY_COUNT++; child = hole * 2; if (child != currentSize && heap[child + 1] < heap[child]) child++; if (heap[child] < tmp) heap[hole] = std::move(heap[child]); else break; } heap[hole] = std::move(tmp); }
template <typename C> void BinaryHeap<C>::printHeap(int index, int offset) const { if (index > currentSize) return; for (int i = 1; i <= offset; i++) cout << ".."; cout << heap[index] << endl; printHeap(2*index, offset + 1); printHeap(2*index+1, offset + 1); return; }
#endif ——————————————————————// BST_HW4.h // KV May 2018, based on // KV replaced exceptions with assert statements;
// version of BST_HW3 that keeps track of insertion and // iteratation costs;
#ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H
//#include "dsexceptions.h" #include <cassert> #include <algorithm> #include <queue> #include <iostream>
using namespace std;
int CLUMSY_COUNT = 0;
template <typename C> class BinarySearchTree { private: struct BinaryNode { C element; BinaryNode *left; BinaryNode *right; BinaryNode *parent; BinaryNode(const C & elem, BinaryNode *lt, BinaryNode *rt, BinaryNode *par) : element(elem), left(lt), right(rt), parent(par) {} }; public: //struct BinaryNode; class iterator {public: iterator() : current{nullptr} {} iterator(BinaryNode * t) : current(t) {} C & operator *() const { return current->element; } bool operator ==(iterator other) const { return current == other.current; } bool operator != (iterator other) const { return current != other.current; } iterator & operator ++() { if (is_root(current)) current = leftmost(current->right); else if (is_left_child(current)) { if (current->left == nullptr && current->right == nullptr) { current = current->parent; CLUMSY_COUNT++; } else if (current->right != nullptr) current = leftmost(current->right); else { //; // should not happen current = current->parent; // NEW!! CLUMSY_COUNT++; } } else if (is_right_child(current)) { if (current->right != nullptr) current = leftmost(current->right);else current = follow_parent_until_leftchild(current); } return *this; } iterator & operator++(int) { iterator old(*this); ++(*this); return old; } protected: BinaryNode * current; /* bool is_right_child(BinaryNode * t) { return (t != nullptr && t->parent == nullptr); } */ bool is_root(BinaryNode *t) { return (t != nullptr && t->parent == nullptr); } bool is_left_child(BinaryNode *t) { assert(t != nullptr); if (t->parent != nullptr && t->parent->left == t) return true; else return false; } bool is_right_child(BinaryNode *t) { assert(t != nullptr); if (t->parent != nullptr && t->parent->right == t) return true; else return false; } BinaryNode * leftmost(BinaryNode *t) { if (t == nullptr) return nullptr; CLUMSY_COUNT++; if (t->left == nullptr) return t; return leftmost(t->left); } BinaryNode * follow_parent_until_leftchild(BinaryNode *t) { if (is_root(t)) return nullptr; CLUMSY_COUNT++; if (is_left_child(t)) return t->parent; return follow_parent_until_leftchild(t->parent); } friend class BinarySearchTree<C>; }; public: BinarySearchTree( ) : root{ nullptr } { } BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr } { root = clone( rhs.root); } BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root } { rhs.root = nullptr; } ~BinarySearchTree( ) { makeEmpty( ); } BinarySearchTree & operator=( const BinarySearchTree & rhs ) { BinarySearchTree copy = rhs; std::swap( *this, copy ); return *this; } BinarySearchTree & operator=( BinarySearchTree && rhs ) { std::swap( root, rhs.root ); return *this; } const C & findMin( ) const { assert(!isEmpty()); return findMin( root )->element; } const C & findMax( ) const { assert(!isEmpty()); return findMax( root )->element; } bool contains( const C & x ) const { return contains( x, root ); } bool isEmpty( ) const { return root == nullptr; } void printTree( ostream & out = cout ) const { if( isEmpty( ) ) out << "Empty tree" << endl; else printTree( root, out ); } void printInternal() { printInternal(root,0); } void makeEmpty( ) { makeEmpty( root ); } iterator insert( const C & x ) { return insert( x, root, root); } iterator insert( C && x ) { return insert( std::move( x ), root, root); } void remove( const C & x ) { remove( x, root ); } iterator begin() const { BinaryNode *t = root; while (t->left != nullptr) t = t->left; iterator beg(t); return beg; } iterator end() const { iterator theend(nullptr); return theend; } int size() const { if (root == nullptr) return 0; return 1 + size(root->left) + size(root->right); } private: BinaryNode *root; iterator insert( const C & x, BinaryNode * & t, BinaryNode * & par ) { if( t == nullptr ) { t = new BinaryNode{ x, nullptr, nullptr, par }; return iterator(t); } else if( x < t->element ) { CLUMSY_COUNT++; return insert( x, t->left, t ); } else if( t->element < x ) { CLUMSY_COUNT++; return insert( x, t->right, t ); } else return iterator(t); // Duplicate; do nothing } iterator insert( C && x, BinaryNode * & t, BinaryNode * & par ) { if( t == nullptr ) { t = new BinaryNode{ std::move( x ), nullptr, nullptr, par }; return iterator(t); } else if( x < t->element ) return insert( std::move( x ), t->left, t ); else if( t->element < x ) return insert( std::move( x ), t->right, t ); else return iterator(t); // Duplicate; do nothing } void remove( const C & x, BinaryNode * & t ) { if( t == nullptr ) return; // Item not found; do nothing if( x < t->element ) remove( x, t->left ); else if( t->element < x ) remove( x, t->right ); else if( t->left != nullptr && t->right != nullptr ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else{ BinaryNode *oldNode = t; if (t->left != nullptr) { t->left->parent = t->parent; t = t->left; } else { if (t->right != 0) t->right->parent = t->parent; t = t->right; } delete oldNode; } } BinaryNode * findMin( BinaryNode *t ) const { if( t == nullptr ) return nullptr; if( t->left == nullptr ) return t; return findMin( t->left ); } BinaryNode * findMax( BinaryNode *t ) const { if( t != nullptr ) while( t->right != nullptr ) t = t->right; return t; } bool contains( const C & x, BinaryNode *t ) const { if( t == nullptr ) return false; else if( x < t->element ) return contains( x, t->left ); else if( t->element < x ) return contains( x, t->right ); else return true; // Match } void makeEmpty( BinaryNode * & t ) { if( t != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; } void printTree( BinaryNode *t, ostream & out ) const { if( t != nullptr ) { printTree( t->left, out );out << t->element << endl; printTree( t->right, out ); } } void printInternal(BinaryNode* t, int offset) { for(int i = 1; i <= offset; i++) cout << ".."; if (t == nullptr) { cout << "#" << endl; return; } cout << t->element << endl; printInternal(t->left, offset + 1); printInternal(t->right, offset + 1); } BinaryNode * clone1(BinaryNode *t) const { if (t == nullptr) return nullptr; else return new BinaryNode(t->element, clone1(t->left), clone1(t->right), nullptr); } void put_parents(BinaryNode * t, BinaryNode * par) const { if (t == nullptr) return; t->parent = par; if (t->left != nullptr) put_parents(t->left, t); if (t->right != nullptr) put_parents(t->right, t); } BinaryNode * clone(BinaryNode *t) const { BinaryNode * theclone = clone1(t); put_parents(theclone, nullptr); return theclone; } int size(BinaryNode* t) const { if (t == nullptr) return 0; return 1 + size(t->left) + size(t->right); } }; #endif
// Random.h // KV, June 2018
// some random number generating utilities
#ifndef RANDOM_H_ #define RANDOM_H_
#include <iostream> #include <cstdlib> #include <ctime> #include <vector> #include <set>
using namespace std;
template <typename Cont> void rand_permute(Cont&);
void rand_seed() { int seed = static_cast<int>(time(0)); srand(seed); }
int rand_int(int a, int b) { return a + rand() % (b - a + 1); }
vector<int> rand_int_vector(int k, int a, int b) { set<int> set_of_k; vector<int> rvec; while (set_of_k.size() < k) { int rv = rand_int(a,b); set_of_k.insert(rv); } // will produce vector without duplicate values; set<int>::iterator itr = set_of_k.begin(); for (; itr != set_of_k.end(); ++itr) rvec.push_back(*itr); rand_permute(rvec); return rvec; }
template <typename Cont> void rand_permute(Cont& vals) { for (int i = 1; i <= vals.size()*3; i++) { int r1 = rand_int(0,vals.size()-1); int r2 = rand_int(0,vals.size()-1); typename Cont::iterator itr1 = vals.begin(); typename Cont::iterator itr2 = vals.begin(); for (int i = 1; i <= r1; i++) ++itr1; for (int i = 2; i <= r2; i++) ++itr2; std::swap(*itr1,*itr2); } return; }
#endif
// THSort_HW4.cpp // comparing the performance of TreeSort vs. HeapSort #include <iostream> #include <vector> #include <cmath> #include <cassert> #include "Random.h" #include "TreeSortHeapSort.h" using namespace std; int main() { vector<int> tosort1; vector<int> comps1; vector<int> comps2; int sum1; int sum2; int numdata = 25; rand_seed(); for (numdata = 10; numdata <= 50; numdata+=5) { sum1 = 0; sum2 = 0; for (int i = 1; i <= 25; i++) { tosort1 = rand_int_vector(numdata,1,1000); vector<int> tosort2(tosort1); int k1,k2; TreeSort(tosort1,k1); assert(tosort1.size() == numdata); HeapSort(tosort2,k2); assert(tosort2.size() == numdata); comps1.push_back(k1); comps2.push_back(k2); sum1 += k1; sum2 += k2; cout << endl; double nlogn = numdata* log10(numdata)/log10(2); int nn = numdata * numdata; double avg1 = (double)sum1 / 25; double avg2 = (double)sum2 / 25; cout << numdata << ", " << (int)avg1 << ", " << (int)avg2 << ", " << (int)nlogn << ", " << nn << endl; } } return 0; }
// BinaryHeap_HW4.h // KV, May 2018, after Weiss, Data Structures textbook
// KV: version for HW4; counts comps for insert and deleteMin;
#ifndef BINARYHEAP_H_ #define BINARYHEAP_H_
#include <cassert> #include "Vector.h" using namespace std;
extern int CLUMSY_COUNT;
template <typename C> class BinaryHeap { public: BinaryHeap() : heap(100), currentSize(0) {} BinaryHeap(int capacity) : heap(capacity), currentSize(0) {} BinaryHeap(const Vector<C>&); bool isEmpty() const { return currentSize == 0; } int size() const { return currentSize; } const C & findMin() const { return heap[1]; } void insert(const C &); void insert(C &&); void deleteMin(); void deleteMin(C &); void makeEmpty() { while (!heap.isEmpty()) heap.pop_back(); currentSize = 0; } void printHeap() const { printHeap(1,0); } private: int currentSize; Vector<C> heap; void buildHeap() { for (int i = currentSize/2; i > 0; i--) percolateDown(i); } void percolateDown(int); void printHeap(int,int) const; };
template <typename C> BinaryHeap<C>::BinaryHeap(const Vector<C>& items) : heap(items.size() + 10), currentSize(items.size()) { for (int i = 0; i < items.size(); i++) heap[i + 1] = items[i]; buildHeap(); }
template <typename C> void BinaryHeap<C>::insert(const C& x) { if (currentSize == heap.size()-1) heap.resize(heap.size()*2); int hole = ++currentSize; C copy = x; heap[0] = std::move(copy); for (; x < heap[hole/2]; hole /= 2) { CLUMSY_COUNT++; heap[hole] = std::move(heap[hole/2]); } heap[hole] = std::move(heap[0]); }
template <typename C> void BinaryHeap<C>::insert(C&& x) { if (currentSize == heap.size()-1) heap.resize(heap.size()*2); int hole = ++currentSize; C copy = x; heap[0] = std::move(copy); for (; x < heap[hole/2]; hole /= 2) heap[hole] = std::move(heap[hole/2]); heap[hole] = std::move(heap[0]); }
template <typename C> void BinaryHeap<C>::deleteMin() { assert(!isEmpty()); heap[1] = std::move(heap[currentSize--]); percolateDown(1); }
template <typename C> void BinaryHeap<C>::deleteMin(C & minItem) { assert(!isEmpty()); minItem = std::move(heap[1]); heap[1] = std::move(heap[currentSize--]); percolateDown(1); }
template <typename C> void BinaryHeap<C>::percolateDown(int hole) { int child; C tmp = std::move(heap[hole]); for (; hole * 2 <= currentSize; hole = child) { CLUMSY_COUNT++; child = hole * 2; if (child != currentSize && heap[child + 1] < heap[child]) child++; if (heap[child] < tmp) heap[hole] = std::move(heap[child]); else break; } heap[hole] = std::move(tmp); }
template <typename C> void BinaryHeap<C>::printHeap(int index, int offset) const { if (index > currentSize) return; for (int i = 1; i <= offset; i++) cout << ".."; cout << heap[index] << endl; printHeap(2*index, offset + 1); printHeap(2*index+1, offset + 1); return; }
#endif ——————————————————————// BST_HW4.h // KV May 2018, based on // KV replaced exceptions with assert statements;
// version of BST_HW3 that keeps track of insertion and // iteratation costs;
#ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H
//#include "dsexceptions.h" #include <cassert> #include <algorithm> #include <queue> #include <iostream>
using namespace std;
int CLUMSY_COUNT = 0;
template <typename C> class BinarySearchTree { private: struct BinaryNode { C element; BinaryNode *left; BinaryNode *right; BinaryNode *parent; BinaryNode(const C & elem, BinaryNode *lt, BinaryNode *rt, BinaryNode *par) : element(elem), left(lt), right(rt), parent(par) {} }; public: //struct BinaryNode; class iterator {public: iterator() : current{nullptr} {} iterator(BinaryNode * t) : current(t) {} C & operator *() const { return current->element; } bool operator ==(iterator other) const { return current == other.current; } bool operator != (iterator other) const { return current != other.current; } iterator & operator ++() { if (is_root(current)) current = leftmost(current->right); else if (is_left_child(current)) { if (current->left == nullptr && current->right == nullptr) { current = current->parent; CLUMSY_COUNT++; } else if (current->right != nullptr) current = leftmost(current->right); else { //; // should not happen current = current->parent; // NEW!! CLUMSY_COUNT++; } } else if (is_right_child(current)) { if (current->right != nullptr) current = leftmost(current->right);else current = follow_parent_until_leftchild(current); } return *this; } iterator & operator++(int) { iterator old(*this); ++(*this); return old; } protected: BinaryNode * current; /* bool is_right_child(BinaryNode * t) { return (t != nullptr && t->parent == nullptr); } */ bool is_root(BinaryNode *t) { return (t != nullptr && t->parent == nullptr); } bool is_left_child(BinaryNode *t) { assert(t != nullptr); if (t->parent != nullptr && t->parent->left == t) return true; else return false; } bool is_right_child(BinaryNode *t) { assert(t != nullptr); if (t->parent != nullptr && t->parent->right == t) return true; else return false; } BinaryNode * leftmost(BinaryNode *t) { if (t == nullptr) return nullptr; CLUMSY_COUNT++; if (t->left == nullptr) return t; return leftmost(t->left); } BinaryNode * follow_parent_until_leftchild(BinaryNode *t) { if (is_root(t)) return nullptr; CLUMSY_COUNT++; if (is_left_child(t)) return t->parent; return follow_parent_until_leftchild(t->parent); } friend class BinarySearchTree<C>; }; public: BinarySearchTree( ) : root{ nullptr } { } BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr } { root = clone( rhs.root); } BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root } { rhs.root = nullptr; } ~BinarySearchTree( ) { makeEmpty( ); } BinarySearchTree & operator=( const BinarySearchTree & rhs ) { BinarySearchTree copy = rhs; std::swap( *this, copy ); return *this; } BinarySearchTree & operator=( BinarySearchTree && rhs ) { std::swap( root, rhs.root ); return *this; } const C & findMin( ) const { assert(!isEmpty()); return findMin( root )->element; } const C & findMax( ) const { assert(!isEmpty()); return findMax( root )->element; } bool contains( const C & x ) const { return contains( x, root ); } bool isEmpty( ) const { return root == nullptr; } void printTree( ostream & out = cout ) const { if( isEmpty( ) ) out << "Empty tree" << endl; else printTree( root, out ); } void printInternal() { printInternal(root,0); } void makeEmpty( ) { makeEmpty( root ); } iterator insert( const C & x ) { return insert( x, root, root); } iterator insert( C && x ) { return insert( std::move( x ), root, root); } void remove( const C & x ) { remove( x, root ); } iterator begin() const { BinaryNode *t = root; while (t->left != nullptr) t = t->left; iterator beg(t); return beg; } iterator end() const { iterator theend(nullptr); return theend; } int size() const { if (root == nullptr) return 0; return 1 + size(root->left) + size(root->right); } private: BinaryNode *root; iterator insert( const C & x, BinaryNode * & t, BinaryNode * & par ) { if( t == nullptr ) { t = new BinaryNode{ x, nullptr, nullptr, par }; return iterator(t); } else if( x < t->element ) { CLUMSY_COUNT++; return insert( x, t->left, t ); } else if( t->element < x ) { CLUMSY_COUNT++; return insert( x, t->right, t ); } else return iterator(t); // Duplicate; do nothing } iterator insert( C && x, BinaryNode * & t, BinaryNode * & par ) { if( t == nullptr ) { t = new BinaryNode{ std::move( x ), nullptr, nullptr, par }; return iterator(t); } else if( x < t->element ) return insert( std::move( x ), t->left, t ); else if( t->element < x ) return insert( std::move( x ), t->right, t ); else return iterator(t); // Duplicate; do nothing } void remove( const C & x, BinaryNode * & t ) { if( t == nullptr ) return; // Item not found; do nothing if( x < t->element ) remove( x, t->left ); else if( t->element < x ) remove( x, t->right ); else if( t->left != nullptr && t->right != nullptr ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else{ BinaryNode *oldNode = t; if (t->left != nullptr) { t->left->parent = t->parent; t = t->left; } else { if (t->right != 0) t->right->parent = t->parent; t = t->right; } delete oldNode; } } BinaryNode * findMin( BinaryNode *t ) const { if( t == nullptr ) return nullptr; if( t->left == nullptr ) return t; return findMin( t->left ); } BinaryNode * findMax( BinaryNode *t ) const { if( t != nullptr ) while( t->right != nullptr ) t = t->right; return t; } bool contains( const C & x, BinaryNode *t ) const { if( t == nullptr ) return false; else if( x < t->element ) return contains( x, t->left ); else if( t->element < x ) return contains( x, t->right ); else return true; // Match } void makeEmpty( BinaryNode * & t ) { if( t != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; } void printTree( BinaryNode *t, ostream & out ) const { if( t != nullptr ) { printTree( t->left, out );out << t->element << endl; printTree( t->right, out ); } } void printInternal(BinaryNode* t, int offset) { for(int i = 1; i <= offset; i++) cout << ".."; if (t == nullptr) { cout << "#" << endl; return; } cout << t->element << endl; printInternal(t->left, offset + 1); printInternal(t->right, offset + 1); } BinaryNode * clone1(BinaryNode *t) const { if (t == nullptr) return nullptr; else return new BinaryNode(t->element, clone1(t->left), clone1(t->right), nullptr); } void put_parents(BinaryNode * t, BinaryNode * par) const { if (t == nullptr) return; t->parent = par; if (t->left != nullptr) put_parents(t->left, t); if (t->right != nullptr) put_parents(t->right, t); } BinaryNode * clone(BinaryNode *t) const { BinaryNode * theclone = clone1(t); put_parents(theclone, nullptr); return theclone; } int size(BinaryNode* t) const { if (t == nullptr) return 0; return 1 + size(t->left) + size(t->right); } }; #endif
// Random.h // KV, June 2018
// some random number generating utilities
#ifndef RANDOM_H_ #define RANDOM_H_
#include <iostream> #include <cstdlib> #include <ctime> #include <vector> #include <set>
using namespace std;
template <typename Cont> void rand_permute(Cont&);
void rand_seed() { int seed = static_cast<int>(time(0)); srand(seed); }
int rand_int(int a, int b) { return a + rand() % (b - a + 1); }
vector<int> rand_int_vector(int k, int a, int b) { set<int> set_of_k; vector<int> rvec; while (set_of_k.size() < k) { int rv = rand_int(a,b); set_of_k.insert(rv); } // will produce vector without duplicate values; set<int>::iterator itr = set_of_k.begin(); for (; itr != set_of_k.end(); ++itr) rvec.push_back(*itr); rand_permute(rvec); return rvec; }
template <typename Cont> void rand_permute(Cont& vals) { for (int i = 1; i <= vals.size()*3; i++) { int r1 = rand_int(0,vals.size()-1); int r2 = rand_int(0,vals.size()-1); typename Cont::iterator itr1 = vals.begin(); typename Cont::iterator itr2 = vals.begin(); for (int i = 1; i <= r1; i++) ++itr1; for (int i = 2; i <= r2; i++) ++itr2; std::swap(*itr1,*itr2); } return; }
#endif
// THSort_HW4.cpp // comparing the performance of TreeSort vs. HeapSort #include <iostream> #include <vector> #include <cmath> #include <cassert> #include "Random.h" #include "TreeSortHeapSort.h" using namespace std; int main() { vector<int> tosort1; vector<int> comps1; vector<int> comps2; int sum1; int sum2; int numdata = 25; rand_seed(); for (numdata = 10; numdata <= 50; numdata+=5) { sum1 = 0; sum2 = 0; for (int i = 1; i <= 25; i++) { tosort1 = rand_int_vector(numdata,1,1000); vector<int> tosort2(tosort1); int k1,k2; TreeSort(tosort1,k1); assert(tosort1.size() == numdata); HeapSort(tosort2,k2); assert(tosort2.size() == numdata); comps1.push_back(k1); comps2.push_back(k2); sum1 += k1; sum2 += k2; cout << endl; double nlogn = numdata* log10(numdata)/log10(2); int nn = numdata * numdata; double avg1 = (double)sum1 / 25; double avg2 = (double)sum2 / 25; cout << numdata << ", " << (int)avg1 << ", " << (int)avg2 << ", " << (int)nlogn << ", " << nn << endl; } } return 0; }
// BinaryHeap_HW4.h // KV, May 2018, after Weiss, Data Structures textbook
// KV: version for HW4; counts comps for insert and deleteMin;
#ifndef BINARYHEAP_H_ #define BINARYHEAP_H_
#include <cassert> #include "Vector.h" using namespace std;
extern int CLUMSY_COUNT;
template <typename C> class BinaryHeap { public: BinaryHeap() : heap(100), currentSize(0) {} BinaryHeap(int capacity) : heap(capacity), currentSize(0) {} BinaryHeap(const Vector<C>&); bool isEmpty() const { return currentSize == 0; } int size() const { return currentSize; } const C & findMin() const { return heap[1]; } void insert(const C &); void insert(C &&); void deleteMin(); void deleteMin(C &); void makeEmpty() { while (!heap.isEmpty()) heap.pop_back(); currentSize = 0; } void printHeap() const { printHeap(1,0); } private: int currentSize; Vector<C> heap; void buildHeap() { for (int i = currentSize/2; i > 0; i--) percolateDown(i); } void percolateDown(int); void printHeap(int,int) const; };
template <typename C> BinaryHeap<C>::BinaryHeap(const Vector<C>& items) : heap(items.size() + 10), currentSize(items.size()) { for (int i = 0; i < items.size(); i++) heap[i + 1] = items[i]; buildHeap(); }
template <typename C> void BinaryHeap<C>::insert(const C& x) { if (currentSize == heap.size()-1) heap.resize(heap.size()*2); int hole = ++currentSize; C copy = x; heap[0] = std::move(copy); for (; x < heap[hole/2]; hole /= 2) { CLUMSY_COUNT++; heap[hole] = std::move(heap[hole/2]); } heap[hole] = std::move(heap[0]); }
template <typename C> void BinaryHeap<C>::insert(C&& x) { if (currentSize == heap.size()-1) heap.resize(heap.size()*2); int hole = ++currentSize; C copy = x; heap[0] = std::move(copy); for (; x < heap[hole/2]; hole /= 2) heap[hole] = std::move(heap[hole/2]); heap[hole] = std::move(heap[0]); }
template <typename C> void BinaryHeap<C>::deleteMin() { assert(!isEmpty()); heap[1] = std::move(heap[currentSize--]); percolateDown(1); }
template <typename C> void BinaryHeap<C>::deleteMin(C & minItem) { assert(!isEmpty()); minItem = std::move(heap[1]); heap[1] = std::move(heap[currentSize--]); percolateDown(1); }
template <typename C> void BinaryHeap<C>::percolateDown(int hole) { int child; C tmp = std::move(heap[hole]); for (; hole * 2 <= currentSize; hole = child) { CLUMSY_COUNT++; child = hole * 2; if (child != currentSize && heap[child + 1] < heap[child]) child++; if (heap[child] < tmp) heap[hole] = std::move(heap[child]); else break; } heap[hole] = std::move(tmp); }
template <typename C> void BinaryHeap<C>::printHeap(int index, int offset) const { if (index > currentSize) return; for (int i = 1; i <= offset; i++) cout << ".."; cout << heap[index] << endl; printHeap(2*index, offset + 1); printHeap(2*index+1, offset + 1); return; }
#endif ——————————————————————// BST_HW4.h // KV May 2018, based on // KV replaced exceptions with assert statements;
// version of BST_HW3 that keeps track of insertion and // iteratation costs;
#ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H
//#include "dsexceptions.h" #include <cassert> #include <algorithm> #include <queue> #include <iostream>
using namespace std;
int CLUMSY_COUNT = 0;
template <typename C> class BinarySearchTree { private: struct BinaryNode { C element; BinaryNode *left; BinaryNode *right; BinaryNode *parent; BinaryNode(const C & elem, BinaryNode *lt, BinaryNode *rt, BinaryNode *par) : element(elem), left(lt), right(rt), parent(par) {} }; public: //struct BinaryNode; class iterator {public: iterator() : current{nullptr} {} iterator(BinaryNode * t) : current(t) {} C & operator *() const { return current->element; } bool operator ==(iterator other) const { return current == other.current; } bool operator != (iterator other) const { return current != other.current; } iterator & operator ++() { if (is_root(current)) current = leftmost(current->right); else if (is_left_child(current)) { if (current->left == nullptr && current->right == nullptr) { current = current->parent; CLUMSY_COUNT++; } else if (current->right != nullptr) current = leftmost(current->right); else { //; // should not happen current = current->parent; // NEW!! CLUMSY_COUNT++; } } else if (is_right_child(current)) { if (current->right != nullptr) current = leftmost(current->right);else current = follow_parent_until_leftchild(current); } return *this; } iterator & operator++(int) { iterator old(*this); ++(*this); return old; } protected: BinaryNode * current; /* bool is_right_child(BinaryNode * t) { return (t != nullptr && t->parent == nullptr); } */ bool is_root(BinaryNode *t) { return (t != nullptr && t->parent == nullptr); } bool is_left_child(BinaryNode *t) { assert(t != nullptr); if (t->parent != nullptr && t->parent->left == t) return true; else return false; } bool is_right_child(BinaryNode *t) { assert(t != nullptr); if (t->parent != nullptr && t->parent->right == t) return true; else return false; } BinaryNode * leftmost(BinaryNode *t) { if (t == nullptr) return nullptr; CLUMSY_COUNT++; if (t->left == nullptr) return t; return leftmost(t->left); } BinaryNode * follow_parent_until_leftchild(BinaryNode *t) { if (is_root(t)) return nullptr; CLUMSY_COUNT++; if (is_left_child(t)) return t->parent; return follow_parent_until_leftchild(t->parent); } friend class BinarySearchTree<C>; }; public: BinarySearchTree( ) : root{ nullptr } { } BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr } { root = clone( rhs.root); } BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root } { rhs.root = nullptr; } ~BinarySearchTree( ) { makeEmpty( ); } BinarySearchTree & operator=( const BinarySearchTree & rhs ) { BinarySearchTree copy = rhs; std::swap( *this, copy ); return *this; } BinarySearchTree & operator=( BinarySearchTree && rhs ) { std::swap( root, rhs.root ); return *this; } const C & findMin( ) const { assert(!isEmpty()); return findMin( root )->element; } const C & findMax( ) const { assert(!isEmpty()); return findMax( root )->element; } bool contains( const C & x ) const { return contains( x, root ); } bool isEmpty( ) const { return root == nullptr; } void printTree( ostream & out = cout ) const { if( isEmpty( ) ) out << "Empty tree" << endl; else printTree( root, out ); } void printInternal() { printInternal(root,0); } void makeEmpty( ) { makeEmpty( root ); } iterator insert( const C & x ) { return insert( x, root, root); } iterator insert( C && x ) { return insert( std::move( x ), root, root); } void remove( const C & x ) { remove( x, root ); } iterator begin() const { BinaryNode *t = root; while (t->left != nullptr) t = t->left; iterator beg(t); return beg; } iterator end() const { iterator theend(nullptr); return theend; } int size() const { if (root == nullptr) return 0; return 1 + size(root->left) + size(root->right); } private: BinaryNode *root; iterator insert( const C & x, BinaryNode * & t, BinaryNode * & par ) { if( t == nullptr ) { t = new BinaryNode{ x, nullptr, nullptr, par }; return iterator(t); } else if( x < t->element ) { CLUMSY_COUNT++; return insert( x, t->left, t ); } else if( t->element < x ) { CLUMSY_COUNT++; return insert( x, t->right, t ); } else return iterator(t); // Duplicate; do nothing } iterator insert( C && x, BinaryNode * & t, BinaryNode * & par ) { if( t == nullptr ) { t = new BinaryNode{ std::move( x ), nullptr, nullptr, par }; return iterator(t); } else if( x < t->element ) return insert( std::move( x ), t->left, t ); else if( t->element < x ) return insert( std::move( x ), t->right, t ); else return iterator(t); // Duplicate; do nothing } void remove( const C & x, BinaryNode * & t ) { if( t == nullptr ) return; // Item not found; do nothing if( x < t->element ) remove( x, t->left ); else if( t->element < x ) remove( x, t->right ); else if( t->left != nullptr && t->right != nullptr ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else{ BinaryNode *oldNode = t; if (t->left != nullptr) { t->left->parent = t->parent; t = t->left; } else { if (t->right != 0) t->right->parent = t->parent; t = t->right; } delete oldNode; } } BinaryNode * findMin( BinaryNode *t ) const { if( t == nullptr ) return nullptr; if( t->left == nullptr ) return t; return findMin( t->left ); } BinaryNode * findMax( BinaryNode *t ) const { if( t != nullptr ) while( t->right != nullptr ) t = t->right; return t; } bool contains( const C & x, BinaryNode *t ) const { if( t == nullptr ) return false; else if( x < t->element ) return contains( x, t->left ); else if( t->element < x ) return contains( x, t->right ); else return true; // Match } void makeEmpty( BinaryNode * & t ) { if( t != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; } void printTree( BinaryNode *t, ostream & out ) const { if( t != nullptr ) { printTree( t->left, out );out << t->element << endl; printTree( t->right, out ); } } void printInternal(BinaryNode* t, int offset) { for(int i = 1; i <= offset; i++) cout << ".."; if (t == nullptr) { cout << "#" << endl; return; } cout << t->element << endl; printInternal(t->left, offset + 1); printInternal(t->right, offset + 1); } BinaryNode * clone1(BinaryNode *t) const { if (t == nullptr) return nullptr; else return new BinaryNode(t->element, clone1(t->left), clone1(t->right), nullptr); } void put_parents(BinaryNode * t, BinaryNode * par) const { if (t == nullptr) return; t->parent = par; if (t->left != nullptr) put_parents(t->left, t); if (t->right != nullptr) put_parents(t->right, t); } BinaryNode * clone(BinaryNode *t) const { BinaryNode * theclone = clone1(t); put_parents(theclone, nullptr); return theclone; } int size(BinaryNode* t) const { if (t == nullptr) return 0; return 1 + size(t->left) + size(t->right); } }; #endif
// Random.h // KV, June 2018
// some random number generating utilities
#ifndef RANDOM_H_ #define RANDOM_H_
#include <iostream> #include <cstdlib> #include <ctime> #include <vector> #include <set>
using namespace std;
template <typename Cont> void rand_permute(Cont&);
void rand_seed() { int seed = static_cast<int>(time(0)); srand(seed); }
int rand_int(int a, int b) { return a + rand() % (b - a + 1); }
vector<int> rand_int_vector(int k, int a, int b) { set<int> set_of_k; vector<int> rvec; while (set_of_k.size() < k) { int rv = rand_int(a,b); set_of_k.insert(rv); } // will produce vector without duplicate values; set<int>::iterator itr = set_of_k.begin(); for (; itr != set_of_k.end(); ++itr) rvec.push_back(*itr); rand_permute(rvec); return rvec; }
template <typename Cont> void rand_permute(Cont& vals) { for (int i = 1; i <= vals.size()*3; i++) { int r1 = rand_int(0,vals.size()-1); int r2 = rand_int(0,vals.size()-1); typename Cont::iterator itr1 = vals.begin(); typename Cont::iterator itr2 = vals.begin(); for (int i = 1; i <= r1; i++) ++itr1; for (int i = 2; i <= r2; i++) ++itr2; std::swap(*itr1,*itr2); } return; }
#endif // Random.h // KV, June 2018
// some random number generating utilities
#ifndef RANDOM_H_ #define RANDOM_H_
#include <iostream> #include <cstdlib> #include <ctime> #include <vector> #include <set>
using namespace std;
template <typename Cont> void rand_permute(Cont&);
void rand_seed() { int seed = static_cast<int>(time(0)); srand(seed); }
int rand_int(int a, int b) { return a + rand() % (b - a + 1); }
vector<int> rand_int_vector(int k, int a, int b) { set<int> set_of_k; vector<int> rvec; while (set_of_k.size() < k) { int rv = rand_int(a,b); set_of_k.insert(rv); } // will produce vector without duplicate values; set<int>::iterator itr = set_of_k.begin(); for (; itr != set_of_k.end(); ++itr) rvec.push_back(*itr); rand_permute(rvec); return rvec; }
template <typename Cont> void rand_permute(Cont& vals) { for (int i = 1; i <= vals.size()*3; i++) { int r1 = rand_int(0,vals.size()-1); int r2 = rand_int(0,vals.size()-1); typename Cont::iterator itr1 = vals.begin(); typename Cont::iterator itr2 = vals.begin(); for (int i = 1; i <= r1; i++) ++itr1; for (int i = 2; i <= r2; i++) ++itr2; std::swap(*itr1,*itr2); } return; }
#endif
// THSort_HW4.cpp // comparing the performance of TreeSort vs. HeapSort #include <iostream> #include <vector> #include <cmath> #include <cassert> #include "Random.h" #include "TreeSortHeapSort.h" using namespace std; int main() { vector<int> tosort1; vector<int> comps1; vector<int> comps2; int sum1; int sum2; int numdata = 25; rand_seed(); for (numdata = 10; numdata <= 50; numdata+=5) { sum1 = 0; sum2 = 0; for (int i = 1; i <= 25; i++) { tosort1 = rand_int_vector(numdata,1,1000); vector<int> tosort2(tosort1); int k1,k2; TreeSort(tosort1,k1); assert(tosort1.size() == numdata); HeapSort(tosort2,k2); assert(tosort2.size() == numdata); comps1.push_back(k1); comps2.push_back(k2); sum1 += k1; sum2 += k2; cout << endl; double nlogn = numdata* log10(numdata)/log10(2); int nn = numdata * numdata; double avg1 = (double)sum1 / 25; double avg2 = (double)sum2 / 25; cout << numdata << ", " << (int)avg1 << ", " << (int)avg2 << ", " << (int)nlogn << ", " << nn << endl; } } return 0; } // THSort_HW4.cpp // comparing the performance of TreeSort vs. HeapSort #include <iostream> #include <vector> #include <cmath> #include <cassert> #include "Random.h" #include "TreeSortHeapSort.h" using namespace std; int main() { vector<int> tosort1; vector<int> comps1; vector<int> comps2; int sum1; int sum2; int numdata = 25; rand_seed(); for (numdata = 10; numdata <= 50; numdata+=5) { sum1 = 0; sum2 = 0; for (int i = 1; i <= 25; i++) { tosort1 = rand_int_vector(numdata,1,1000); vector<int> tosort2(tosort1); int k1,k2; TreeSort(tosort1,k1); assert(tosort1.size() == numdata); HeapSort(tosort2,k2); assert(tosort2.size() == numdata); comps1.push_back(k1); comps2.push_back(k2); sum1 += k1; sum2 += k2; cout << endl; double nlogn = numdata* log10(numdata)/log10(2); int nn = numdata * numdata; double avg1 = (double)sum1 / 25; double avg2 = (double)sum2 / 25; cout << numdata << ", " << (int)avg1 << ", " << (int)avg2 << ", " << (int)nlogn << ", " << nn << endl; } } return 0; }
Explanation / Answer
// BinaryHeap_HW4.h
// KV, May 2018, after Weiss, Data Structures textbook
// KV: version for HW4; counts comps for insert and deleteMin;
#ifndef BINARYHEAP_H_
#define BINARYHEAP_H_
#include <cassert>
#include "Vector.h"
using namespace std;
extern int CLUMSY_COUNT;
template <typename C>
class BinaryHeap
{
public:
BinaryHeap()
: heap(100), currentSize(0)
{}
BinaryHeap(int capacity)
: heap(capacity), currentSize(0)
{}
BinaryHeap(const Vector<C>&);
bool isEmpty() const
{
return currentSize == 0;
}
int size() const
{
return currentSize;
}
const C & findMin() const
{
return heap[1];
}
void insert(const C &);
void insert(C &&);
void deleteMin();
void deleteMin(C &);
void makeEmpty()
{
while (!heap.isEmpty())
heap.pop_back();
currentSize = 0;
}
void printHeap() const
{
printHeap(1,0);
}
private:
int currentSize;
Vector<C> heap;
void buildHeap()
{
for (int i = currentSize/2; i > 0; i--)
percolateDown(i);
}
void percolateDown(int);
void printHeap(int,int) const;
};
template <typename C>
BinaryHeap<C>::BinaryHeap(const Vector<C>& items)
: heap(items.size() + 10), currentSize(items.size())
{
for (int i = 0; i < items.size(); i++)
heap[i + 1] = items[i];
buildHeap();
}
template <typename C>
void BinaryHeap<C>::insert(const C& x)
{
if (currentSize == heap.size()-1)
heap.resize(heap.size()*2);
int hole = ++currentSize;
C copy = x;
heap[0] = std::move(copy);
for (; x < heap[hole/2]; hole /= 2)
{
CLUMSY_COUNT++;
heap[hole] = std::move(heap[hole/2]);
}
heap[hole] = std::move(heap[0]);
}
template <typename C>
void BinaryHeap<C>::insert(C&& x)
{
if (currentSize == heap.size()-1)
heap.resize(heap.size()*2);
int hole = ++currentSize;
C copy = x;
heap[0] = std::move(copy);
for (; x < heap[hole/2]; hole /= 2)
heap[hole] = std::move(heap[hole/2]);
heap[hole] = std::move(heap[0]);
}
template <typename C>
void BinaryHeap<C>::deleteMin()
{
assert(!isEmpty());
heap[1] = std::move(heap[currentSize--]);
percolateDown(1);
}
template <typename C>
void BinaryHeap<C>::deleteMin(C & minItem)
{
assert(!isEmpty());
minItem = std::move(heap[1]);
heap[1] = std::move(heap[currentSize--]);
percolateDown(1);
}
template <typename C>
void BinaryHeap<C>::percolateDown(int hole)
{
int child;
C tmp = std::move(heap[hole]);
for (; hole * 2 <= currentSize; hole = child)
{
CLUMSY_COUNT++;
child = hole * 2;
if (child != currentSize && heap[child + 1] < heap[child])
child++;
if (heap[child] < tmp)
heap[hole] = std::move(heap[child]);
else
break;
}
heap[hole] = std::move(tmp);
}
template <typename C>
void BinaryHeap<C>::printHeap(int index, int offset) const
{
if (index > currentSize)
return;
for (int i = 1; i <= offset; i++)
cout << "..";
cout << heap[index] << endl;
printHeap(2*index, offset + 1);
printHeap(2*index+1, offset + 1);
return;
}
#endif
——————————————————————// BST_HW4.h
// KV May 2018, based on
// KV replaced exceptions with assert statements;
// version of BST_HW3 that keeps track of insertion and
// iteratation costs;
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
//#include "dsexceptions.h"
#include <cassert>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
int CLUMSY_COUNT = 0;
template <typename C>
class BinarySearchTree
{
private:
struct BinaryNode
{
C element;
BinaryNode *left;
BinaryNode *right;
BinaryNode *parent;
BinaryNode(const C & elem, BinaryNode *lt,
BinaryNode *rt,
BinaryNode *par)
: element(elem), left(lt), right(rt), parent(par)
{}
};
public:
//struct BinaryNode;
class iterator
{public:
iterator() : current{nullptr}
{}
iterator(BinaryNode * t) : current(t)
{}
C & operator *() const
{
return current->element;
}
bool operator ==(iterator other) const
{
return current == other.current;
}
bool operator != (iterator other) const
{
return current != other.current;
}
iterator & operator ++()
{
if (is_root(current))
current = leftmost(current->right);
else if (is_left_child(current))
{
if (current->left == nullptr && current->right
== nullptr)
{
current = current->parent;
CLUMSY_COUNT++;
}
else if (current->right != nullptr)
current = leftmost(current->right);
else
{
//; // should not happen
current = current->parent; // NEW!!
CLUMSY_COUNT++;
}
}
else if (is_right_child(current))
{
if (current->right != nullptr)
current = leftmost(current->right);else
current = follow_parent_until_leftchild(current);
}
return *this;
}
iterator & operator++(int)
{
iterator old(*this);
++(*this);
return old;
}
protected:
BinaryNode * current;
/*
bool is_right_child(BinaryNode * t)
{
return (t != nullptr && t->parent == nullptr);
}
*/
bool is_root(BinaryNode *t)
{
return (t != nullptr && t->parent == nullptr);
}
bool is_left_child(BinaryNode *t)
{
assert(t != nullptr);
if (t->parent != nullptr && t->parent->left == t)
return true;
else
return false;
}
bool is_right_child(BinaryNode *t)
{
assert(t != nullptr);
if (t->parent != nullptr && t->parent->right ==
t)
return true;
else
return false;
}
BinaryNode * leftmost(BinaryNode *t)
{
if (t == nullptr)
return nullptr;
CLUMSY_COUNT++;
if (t->left == nullptr)
return t;
return leftmost(t->left);
}
BinaryNode * follow_parent_until_leftchild(BinaryNode *t)
{
if (is_root(t))
return nullptr;
CLUMSY_COUNT++;
if (is_left_child(t))
return t->parent;
return follow_parent_until_leftchild(t->parent);
}
friend class BinarySearchTree<C>;
};
public:
BinarySearchTree( ) : root{ nullptr }
{
}
BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr }
{
root = clone( rhs.root);
}
BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root }
{
rhs.root = nullptr;
}
~BinarySearchTree( )
{
makeEmpty( );
}
BinarySearchTree & operator=( const BinarySearchTree & rhs )
{
BinarySearchTree copy = rhs;
std::swap( *this, copy );
return *this;
}
BinarySearchTree & operator=( BinarySearchTree && rhs )
{
std::swap( root, rhs.root );
return *this;
}
const C & findMin( ) const
{
assert(!isEmpty());
return findMin( root )->element;
}
const C & findMax( ) const
{
assert(!isEmpty());
return findMax( root )->element;
}
bool contains( const C & x ) const
{
return contains( x, root );
}
bool isEmpty( ) const
{
return root == nullptr;
}
void printTree( ostream & out = cout ) const
{
if( isEmpty( ) )
out << "Empty tree" << endl;
else
printTree( root, out );
}
void printInternal()
{
printInternal(root,0);
}
void makeEmpty( )
{
makeEmpty( root );
}
iterator insert( const C & x )
{
return insert( x, root, root);
}
iterator insert( C && x )
{
return insert( std::move( x ), root, root);
}
void remove( const C & x )
{
remove( x, root );
}
iterator begin() const
{
BinaryNode *t = root;
while (t->left != nullptr)
t = t->left;
iterator beg(t);
return beg;
}
iterator end() const
{
iterator theend(nullptr);
return theend;
}
int size() const
{
if (root == nullptr)
return 0;
return 1 + size(root->left) + size(root->right);
}
private:
BinaryNode *root;
iterator insert( const C & x, BinaryNode * & t,
BinaryNode * & par )
{
if( t == nullptr )
{
t = new BinaryNode{ x, nullptr, nullptr, par };
return iterator(t);
}
else if( x < t->element )
{
CLUMSY_COUNT++;
return insert( x, t->left, t );
}
else if( t->element < x )
{
CLUMSY_COUNT++;
return insert( x, t->right, t );
}
else
return iterator(t); // Duplicate; do nothing
}
iterator insert( C && x, BinaryNode * & t, BinaryNode *
& par )
{
if( t == nullptr )
{
t = new BinaryNode{ std::move( x ), nullptr,
nullptr, par };
return iterator(t);
}
else if( x < t->element )
return insert( std::move( x ), t->left, t );
else if( t->element < x )
return insert( std::move( x ), t->right, t );
else
return iterator(t); // Duplicate; do nothing
}
void remove( const C & x, BinaryNode * & t )
{
if( t == nullptr )
return;
// Item not found; do nothing
if( x < t->element )
remove( x, t->left );
else if( t->element < x )
remove( x, t->right );
else if( t->left != nullptr && t->right !=
nullptr ) // Two children
{
t->element = findMin( t->right )->element;
remove( t->element, t->right );
}
else{
BinaryNode *oldNode = t;
if (t->left != nullptr)
{
t->left->parent = t->parent;
t = t->left;
}
else
{
if (t->right != 0)
t->right->parent = t->parent;
t = t->right;
}
delete oldNode;
}
}
BinaryNode * findMin( BinaryNode *t ) const
{
if( t == nullptr )
return nullptr;
if( t->left == nullptr )
return t;
return findMin( t->left );
}
BinaryNode * findMax( BinaryNode *t ) const
{
if( t != nullptr )
while( t->right != nullptr )
t = t->right;
return t;
}
bool contains( const C & x, BinaryNode *t ) const
{
if( t == nullptr )
return false;
else if( x < t->element )
return contains( x, t->left );
else if( t->element < x )
return contains( x, t->right );
else
return true;
// Match
}
void makeEmpty( BinaryNode * & t )
{
if( t != nullptr )
{
makeEmpty( t->left );
makeEmpty( t->right );
delete t;
}
t = nullptr;
}
void printTree( BinaryNode *t, ostream & out )
const
{
if( t != nullptr )
{
printTree( t->left, out );out << t->element << endl;
printTree( t->right, out );
}
}
void printInternal(BinaryNode* t, int offset)
{
for(int i = 1; i <= offset; i++)
cout << "..";
if (t == nullptr)
{
cout << "#" << endl;
return;
}
cout << t->element << endl;
printInternal(t->left, offset + 1);
printInternal(t->right, offset + 1);
}
BinaryNode * clone1(BinaryNode *t) const
{
if (t == nullptr)
return nullptr;
else
return new BinaryNode(t->element, clone1(t->left),
clone1(t->right), nullptr);
}
void put_parents(BinaryNode * t, BinaryNode * par)
const
{
if (t == nullptr)
return;
t->parent = par;
if (t->left != nullptr)
put_parents(t->left, t);
if (t->right != nullptr)
put_parents(t->right, t);
}
BinaryNode * clone(BinaryNode *t) const
{
BinaryNode * theclone = clone1(t);
put_parents(theclone, nullptr);
return theclone;
}
int size(BinaryNode* t) const
{
if (t == nullptr)
return 0;
return 1 + size(t->left) + size(t->right);
}
};
#endif
// Random.h
// KV, June 2018
// some random number generating utilities
#ifndef RANDOM_H_
#define RANDOM_H_
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <set>
using namespace std;
template <typename Cont>
void rand_permute(Cont&);
void rand_seed()
{
int seed = static_cast<int>(time(0));
srand(seed);
}
int rand_int(int a, int b)
{
return a + rand() % (b - a + 1);
}
vector<int> rand_int_vector(int k, int a, int b)
{
set<int> set_of_k;
vector<int> rvec;
while (set_of_k.size() < k)
{
int rv = rand_int(a,b);
set_of_k.insert(rv);
}
// will produce vector without duplicate values;
set<int>::iterator itr = set_of_k.begin();
for (; itr != set_of_k.end(); ++itr)
rvec.push_back(*itr);
rand_permute(rvec);
return rvec;
}
template <typename Cont>
void rand_permute(Cont& vals)
{
for (int i = 1; i <= vals.size()*3; i++)
{
int r1 = rand_int(0,vals.size()-1);
int r2 = rand_int(0,vals.size()-1);
typename Cont::iterator itr1 = vals.begin();
typename Cont::iterator itr2 = vals.begin();
for (int i = 1; i <= r1; i++) ++itr1;
for (int i = 2; i <= r2; i++) ++itr2;
std::swap(*itr1,*itr2);
}
return;
}
#endif
// THSort_HW4.cpp
// comparing the performance of TreeSort vs. HeapSort
#include <iostream>
#include <vector>
#include <cmath>
#include <cassert>
#include "Random.h"
#include "TreeSortHeapSort.h"
using namespace std;
int main()
{
vector<int> tosort1;
vector<int> comps1;
vector<int> comps2;
int sum1;
int sum2;
int numdata = 25;
rand_seed();
for (numdata = 10; numdata <= 50; numdata+=5)
{ sum1 = 0;
sum2 = 0;
for (int i = 1; i <= 25; i++)
{ tosort1 = rand_int_vector(numdata,1,1000);
vector<int> tosort2(tosort1);
int k1,k2;
TreeSort(tosort1,k1);
assert(tosort1.size() == numdata);
HeapSort(tosort2,k2);
assert(tosort2.size() == numdata);
comps1.push_back(k1);
comps2.push_back(k2);
sum1 += k1;
sum2 += k2;
cout << endl;
double nlogn = numdata* log10(numdata)/log10(2); int nn = numdata * numdata;
double avg1 = (double)sum1 / 25;
double avg2 = (double)sum2 / 25;
cout << numdata << ", " << (int)avg1 << ", " << (int)avg2 << ", " << (int)nlogn
<< ", " << nn << endl;
}
}
return 0;
}
NOTE: You have not asked any question on this post. Kindly update the question with the problem and I will try to answer it. For time being, I am attaching back the code provided by you.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.