diff options
author | Santo Cariotti <santo@dcariotti.me> | 2023-01-07 20:52:02 +0100 |
---|---|---|
committer | Santo Cariotti <santo@dcariotti.me> | 2023-01-07 20:52:02 +0100 |
commit | 3641468ce7e8c1456d21d01e69595a183e93d094 (patch) | |
tree | fab1d71ed7a9c8ad178467adf6d4716d694dcc14 /Year_2 | |
parent | b4728ed55ae16f04cf59f3a9f4c3e7fc7dcb5a39 (diff) |
Add exercise
Diffstat (limited to 'Year_2')
-rw-r--r-- | Year_2/Algorithms/build-max-heap.cc | 138 |
1 files changed, 138 insertions, 0 deletions
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 <cstdlib> +#include <fstream> +#include <iostream> + +using namespace std; + +template <class H> +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<bool>* mh = new MaxHeap<bool>(arr, n, fout); + + delete mh; + } else if (t == "double") { + double* arr = new double[n]; + for (j = 0; j < n; ++j) + fin >> arr[j]; + + MaxHeap<double>* mh = new MaxHeap<double>(arr, n, fout); + + delete mh; + } else if (t == "char") { + char* arr = new char[n]; + for (j = 0; j < n; ++j) + fin >> arr[j]; + + MaxHeap<char>* mh = new MaxHeap<char>(arr, n, fout); + + delete mh; + } else if (t == "int") { + int* arr = new int[n]; + for (j = 0; j < n; ++j) + fin >> arr[j]; + + MaxHeap<int>* mh = new MaxHeap<int>(arr, n, fout); + + delete mh; + } + } + + fin.close(); + fout.close(); + return 0; +} |