From 3641468ce7e8c1456d21d01e69595a183e93d094 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sat, 7 Jan 2023 20:52:02 +0100 Subject: Add exercise --- Year_2/Algorithms/build-max-heap.cc | 138 ++++++++++++++++++++++++++++++++++++ 1 file changed, 138 insertions(+) create mode 100644 Year_2/Algorithms/build-max-heap.cc diff --git a/Year_2/Algorithms/build-max-heap.cc b/Year_2/Algorithms/build-max-heap.cc new file mode 100644 index 0000000..40c0893 --- /dev/null +++ b/Year_2/Algorithms/build-max-heap.cc @@ -0,0 +1,138 @@ +#include +#include +#include + +using namespace std; + +template +class MaxHeap { +public: + void + max_heapify(int i) + { + if (i > _size) + return; + + size_t l = left(i); + size_t r = right(i); + size_t max = i; + + if (l <= _size && _A[l] > _A[i]) + max = l; + if (r <= _size && _A[r] > _A[max]) + max = r; + + if (max != i) { + swap(i, max); + max_heapify(max); + } + } + + size_t + left(int i) + { + return i << 1; + } + size_t + right(int i) + { + return (i << 1) | 1; + } + + ~MaxHeap() + { + delete _A; + } + + MaxHeap(H* A, int size, ostream& out) + : _size(size + 1) + { + _A = new H[_size + 1]; + for (int i = 1; i <= size; ++i) { + _A[i] = A[i - 1]; + } + + for (int i = _size / 2; i > 0; --i) + max_heapify(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; + } + + H + extract_max() + { + swap(1, _size); + --_size; + max_heapify(1); + + return _A[_size + 1]; + } + +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]; + + MaxHeap* mh = new MaxHeap(arr, n, fout); + + delete mh; + } else if (t == "double") { + double* arr = new double[n]; + for (j = 0; j < n; ++j) + fin >> arr[j]; + + MaxHeap* mh = new MaxHeap(arr, n, fout); + + delete mh; + } else if (t == "char") { + char* arr = new char[n]; + for (j = 0; j < n; ++j) + fin >> arr[j]; + + MaxHeap* mh = new MaxHeap(arr, n, fout); + + delete mh; + } else if (t == "int") { + int* arr = new int[n]; + for (j = 0; j < n; ++j) + fin >> arr[j]; + + MaxHeap* mh = new MaxHeap(arr, n, fout); + + delete mh; + } + } + + fin.close(); + fout.close(); + return 0; +} -- cgit v1.2.3-18-g5258