From de5ca5955666edafb86e2e89f9b0774834939bec Mon Sep 17 00:00:00 2001
From: Santo Cariotti <santo@dcariotti.me>
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 <cmath>
+#include <cstdlib>
+#include <fstream>
+#include <iostream>
+
+using namespace std;
+
+template <class H>
+class MinHeap {
+public:
+ MinHeap<H>*
+ 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<bool>* mh = new MinHeap<bool>(arr, n, fout);
+
+ delete mh;
+ } else if (t == "double") {
+ double* arr = new double[n];
+ for (j = 0; j < n; ++j)
+ fin >> arr[j];
+
+ MinHeap<double>* mh = new MinHeap<double>(arr, n, fout);
+
+ delete mh;
+ } else if (t == "char") {
+ char* arr = new char[n];
+ for (j = 0; j < n; ++j)
+ fin >> arr[j];
+
+ MinHeap<char>* mh = new MinHeap<char>(arr, n, fout);
+
+ delete mh;
+ } else if (t == "int") {
+ int* arr = new int[n];
+ for (j = 0; j < n; ++j)
+ fin >> arr[j];
+
+ MinHeap<int>* mh = new MinHeap<int>(arr, n, fout);
+
+ delete mh;
+ }
+ }
+
+ fin.close();
+ fout.close();
+ return 0;
+}
--
cgit v1.2.3-18-g5258