From de5ca5955666edafb86e2e89f9b0774834939bec Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Fri, 13 Jan 2023 18:59:46 +0100 Subject: Add min-enqueue --- Year_2/Algorithms/min-enqueue.cc | 125 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 125 insertions(+) create mode 100644 Year_2/Algorithms/min-enqueue.cc (limited to 'Year_2/Algorithms') diff --git a/Year_2/Algorithms/min-enqueue.cc b/Year_2/Algorithms/min-enqueue.cc new file mode 100644 index 0000000..d6c9db5 --- /dev/null +++ b/Year_2/Algorithms/min-enqueue.cc @@ -0,0 +1,125 @@ +#include +#include +#include +#include + +using namespace std; + +template +class MinHeap { +public: + MinHeap* + enqueue(H key) + { + if (_size == _n) + return this; + ++_size; + _A[_size] = key; + + int i = _size; + int j = i / 2; + + while (i > 1 && _A[i] < _A[j]) { + swap(i, j); + i = j; + j /= 2; + } + + return this; + } + + size_t + left(int i) + { + return i * 2; + } + size_t + right(int i) + { + return i * 2 + 1; + } + + ~MinHeap() + { + delete _A; + } + + MinHeap(H* A, int size, ostream& out) + : _n(size + 1) + { + _A = new H[_n]; + for (int i = 0; i < size; ++i) { + enqueue(A[i]); + } + + for (int i = 1; i <= size; ++i) { + out << _A[i] << ' '; + } + out << endl; + } + + void + swap(int x, int y) + { + auto t = _A[x]; + _A[x] = _A[y]; + _A[y] = t; + } + +private: + H* _A; + size_t _size; + size_t _n; +}; + +int +main(int argc, char** argv) +{ + ifstream fin("input.txt"); + ofstream fout("output.txt"); + string t; + int n, j; + + for (int i = 0; i < atoi(argv[1]); ++i) { + fin >> t; + fin >> n; + + if (t == "bool") { + bool* arr = new bool[n]; + for (j = 0; j < n; ++j) + fin >> arr[j]; + + MinHeap* mh = new MinHeap(arr, n, fout); + + delete mh; + } else if (t == "double") { + double* arr = new double[n]; + for (j = 0; j < n; ++j) + fin >> arr[j]; + + MinHeap* mh = new MinHeap(arr, n, fout); + + delete mh; + } else if (t == "char") { + char* arr = new char[n]; + for (j = 0; j < n; ++j) + fin >> arr[j]; + + MinHeap* mh = new MinHeap(arr, n, fout); + + delete mh; + } else if (t == "int") { + int* arr = new int[n]; + for (j = 0; j < n; ++j) + fin >> arr[j]; + + MinHeap* mh = new MinHeap(arr, n, fout); + + delete mh; + } + } + + fin.close(); + fout.close(); + return 0; +} -- cgit v1.2.3-18-g5258