From 3641468ce7e8c1456d21d01e69595a183e93d094 Mon Sep 17 00:00:00 2001
From: Santo Cariotti <santo@dcariotti.me>
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

(limited to 'Year_2/Algorithms')

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;
+}
-- 
cgit v1.2.3-18-g5258