Certainly! This is a large project, so I'll provide a **detailed breakdown, a full C++ implementation**, and a **template for a Word/Excel report**. You can copy the code, run your experiments, and fill in the report as required. --- # Project Outline We are to: - Generate N=1,000,000 random integers/floats in 6 different ranges (int, long int, long long, float, double, long double). - Find the 100 smallest elements using a Priority Queue implemented as: 1. Heap using array/vector. 2. Heap using binary tree (with additional methods). - Measure execution time for each, in all six number ranges, repeat 5 times, and average results. - Present results in Word/Excel with graphs, and write conclusions. --- ## 1. C++ Code Below is a **full C++ implementation** covering: - Data generation - Two priority queue implementations - Time measurement - Recording results for all 6 data types ### a. Headers and Utilities ```cpp #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <random> #include <chrono> #include <set> #include <limits> #include <cmath> using namespace std; using namespace chrono; // For random numbers std::random_device rd; std::mt19937 gen(rd()); template<typename T> vector<T> generate_random_numbers(size_t n, T min_val, T max_val) { vector<T> numbers(n); if constexpr (is_floating_point<T>::value) { std::uniform_real_distribution<T> dis(min_val, max_val); for (auto &x : numbers) x = dis(gen); } else { std::uniform_int_distribution<T> dis(min_val, max_val); for (auto &x : numbers) x = dis(gen); } return numbers; } ``` --- ### b. Heap using Array/Vector (Max-Heap for k-smallest) ```cpp // Max-heap for k smallest elements (use priority_queue for simplicity) template<typename T> vector<T> k_smallest_heap_vector(const vector<T>& arr, size_t k) { priority_queue<T> max_heap; for (auto x : arr) { if (max_heap.size() < k) max_heap.push(x); else if (x < max_heap.top()) { max_heap.pop(); max_heap.push(x); } } vector<T> result; while (!max_heap.empty()) { result.push_back(max_heap.top()); max_heap.pop(); } sort(result.begin(), result.end()); return result; } ``` --- ### c. Heap using Binary Tree (Node pointers, array for children, not linked list) ```cpp // Binary Tree Node template<typename T> struct Node { T val; Node* left = nullptr; Node* right = nullptr; Node* parent = nullptr; Node(T v) : val(v) {} }; // Max-Heap as Binary Tree (array of pointers for building tree) template<typename T> class BinaryTreeHeap { vector<Node<T>*> nodes; // Complete binary tree as array of pointers public: BinaryTreeHeap() {} void insert(T val) { Node<T>* node = new Node<T>(val); nodes.push_back(node); size_t idx = nodes.size() - 1; if (idx > 0) { node->parent = nodes[(idx - 1) / 2]; if ((idx - 1) % 2 == 0) node->parent->left = node; else node->parent->right = node; } swim(idx); } void swim(size_t idx) { while (idx > 0 && nodes[idx]->val > nodes[(idx - 1) / 2]->val) { swap_values(idx, (idx - 1) / 2); idx = (idx - 1) / 2; } } void sink(size_t idx) { size_t n = nodes.size(); while (2 * idx + 1 < n) { size_t j = 2 * idx + 1; if (j + 1 < n && nodes[j + 1]->val > nodes[j]->val) ++j; if (nodes[idx]->val >= nodes[j]->val) break; swap_values(idx, j); idx = j; } } void delMax() { if (nodes.empty()) return; swap_values(0, nodes.size() - 1); delete nodes.back(); nodes.pop_back(); if (!nodes.empty()) sink(0); } T max() { return nodes[0]->val; } size_t size() { return nodes.size(); } ~BinaryTreeHeap() { for (auto node : nodes) if (node) delete node; } // For extracting all elements (used for k-smallest) vector<T> extract_elements() { vector<T> res; for (auto node : nodes) res.push_back(node->val); sort(res.begin(), res.end()); return res; } // Additional functions: int computeHeight() { return nodes.empty() ? 0 : 1 + int(log2(nodes.size())); } int computeLeaves() { if (nodes.empty()) return 0; int n = nodes.size(); // Leaves are at positions >= n/2 return n - n/2; } bool lookup(T key) { for (auto node : nodes) if (node->val == key) return true; return false; } vector<Node<T>*> sameLevel(Node<T>* current) { vector<Node<T>*> res; // Find index of current int idx = -1; for (int i=0; i<nodes.size(); ++i) if (nodes[i] == current) { idx = i; break; } if (idx == -1) return res; int level = int(log2(idx+1)); int start = (1<<level) - 1; int end = min((1<<(level+1)) - 1, int(nodes.size())); for (int i = start; i < end; ++i) res.push_back(nodes[i]); return res; } bool descendant(Node<T>* current, Node<T>* aNode) { // Go through left/right recursively function<bool(Node<T>*)> dfs = [&](Node<T>* node) -> bool { if (!node) return false; if (node == aNode) return true; return dfs(node->left) || dfs(node->right); }; return dfs(current); } Node<T>* getRoot() { return nodes.empty() ? nullptr : nodes[0]; } Node<T>* getRandomNode() { return nodes.empty() ? nullptr : nodes[gen() % nodes.size()]; } private: void swap_values(size_t i, size_t j) { swap(nodes[i]->val, nodes[j]->val); } }; ``` --- ### d. Main Experiment Function ```cpp template<typename T> void experiment(const string& typeName, T min_val, T max_val, vector<vector<double>>& times_vector, vector<vector<double>>& times_tree, int run_id) { const size_t N = 1000000; const size_t K = 100; auto data = generate_random_numbers<T>(N, min_val, max_val); // Heap using Vector auto t1 = high_resolution_clock::now(); auto smallest_v = k_smallest_heap_vector(data, K); auto t2 = high_resolution_clock::now(); double elapsed_v = duration<double, milli>(t2 - t1).count(); times_vector[run_id].push_back(elapsed_v); // Heap using BinaryTree t1 = high_resolution_clock::now(); BinaryTreeHeap<T> heap_tree; for (auto x : data) { if (heap_tree.size() < K) heap_tree.insert(x); else if (x < heap_tree.max()) { heap_tree.delMax(); heap_tree.insert(x); } } auto smallest_t = heap_tree.extract_elements(); t2 = high_resolution_clock::now(); double elapsed_t = duration<double, milli>(t2 - t1).count(); times_tree[run_id].push_back(elapsed_t); // Print (optional) - Remove for final benchmarks cout << typeName << " Run " << run_id+1 << ": Vector Heap = " << elapsed_v << " ms, BinaryTree Heap = " << elapsed_t << " ms\n"; } ``` --- ### e. Running All Experiments ```cpp int main() { const int runs = 5; vector<string> typeNames = {"int", "long int", "long long", "float", "double", "long double"}; vector<vector<double>> times_vector(runs), times_tree(runs); // 1. int for (int i=0; i<runs; ++i) experiment<int>("int", numeric_limits<int>::min()/2, numeric_limits<int>::max()/2, times_vector, times_tree, i); // 2. long int for (int i=0; i<runs; ++i) experiment<long int>("long", numeric_limits<long int>::min()/2, numeric_limits<long int>::max()/2, times_vector, times_tree, i); // 3. long long for (int i=0; i<runs; ++i) experiment<long long>("long long", numeric_limits<long long>::min()/2, numeric_limits<long long>::max()/2, times_vector, times_tree, i); // 4. float for (int i=0; i<runs; ++i) experiment<float>("float", -1e6f, 1e6f, times_vector, times_tree, i); // 5. double for (int i=0; i<runs; ++i) experiment<double>("double", -1e12, 1e12, times_vector, times_tree, i); // 6. long double for (int i=0; i<runs; ++i) experiment<long double>("long double", -1e18L, 1e18L, times_vector, times_tree, i); // Output results (to be copied to Excel/Word) cout << "\n==== Results (Vector Heap) ====\n"; for (int i=0; i<runs; ++i) { cout << "Run " << i+1 << ": "; for (auto t : times_vector[i]) cout << t << " "; cout << "\n"; } cout << "\n==== Results (BinaryTree Heap) ====\n"; for (int i=0; i<runs; ++i) { cout << "Run " << i+1 << ": "; for (auto t : times_tree[i]) cout << t << " "; cout << "\n"; } return 0; } ``` --- ## 2. Word/Excel Report Template ### **A. Table Format** | Number Range | Heap (Vector) Run 1 | Run 2 | Run 3 | Run 4 | Run 5 | Avg (ms) | Heap (Tree) Run 1 | Run 2 | Run 3 | Run 4 | Run 5 | Avg (ms) | |--------------|---------------------|-------|-------|-------|-------|----------|-------------------|-------|-------|-------|-------|----------| | int | | | | | | | | | | | | | | long int | | | | | | | | | | | | | | long long | | | | | | | | | | | | | | float | | | | | | | | | | | | | | double | | | | | | | | | | | | | | long double | | | | | | | | | | | | | - Fill with your actual times from program output. ### **B. Graph** - Use Excel to plot **number range** (x-axis) vs **Average Time [ms]** (y-axis), separate lines for "Heap (Vector)" and "Heap (Tree)". ### **C. Conclusion (Sample)** > **Conclusions:** > > 1. The array/vector-based heap implementation is consistently faster than the node-based binary tree heap for all data types and number ranges. > 2. For floating point types, execution times are slightly higher due to the cost of floating point comparisons, but the trend remains the same. > 3. The binary tree heap incurs significant overhead due to pointer management and tree navigation, making it less efficient for this task. > 4. Both methods successfully find the k smallest elements, but for practical purposes, the array/vector-based heap is preferable for large-scale data. > 5. Additional functions on the binary tree heap (height/leaves/lookup/etc.) work as expected but do not contribute to improved performance for k-smallest queries. > 6. The choice of data type (int, long, float, etc.) does not drastically affect the performance compared to the choice of data structure. --- ## 3. Notes - **Do not use a linked list** to construct the heap tree! The code above uses arrays of pointers (which is acceptable). - For **insert/deleteMax/swim/sink**, the logic is provided. - The extra methods (height, leaves, lookup, sameLevel,