This is a **large-scale programming/data analysis project** involving data generation, algorithm implementation, performance measurement, and results presentation. Here, I'll break down the steps, provide **code samples** (in C++), and outline the **report format** you would submit in Word/Excel. --- --- ## **Step 1: Data Generation** Generate **1,000,000** random numbers (integers or floats, depending on the data type) and store them in an array/vector. ### **Number Ranges & Types** You’ll run all experiments for these number types: 1. `int` 2. `long int` 3. `long long int` 4. `float` 5. `double` 6. `long double` --- ## **Step 2: Find 100 Smallest Elements** Implement a **priority queue** using: - a) Heap using array/vector - b) Heap using binary tree (node-based, not linked list) You need to: - Implement `insert` and `delMax` for the priority queue - For **binary tree heap**, also implement: - `computeHeight` - `computeLeaves` - `lookup(int key)` - `sameLevel(Node* current)` - `descendant(Node* current, Node* aNode)` --- ## **Step 3: Measure Execution Time** - For each of the 6 number types, **run the algorithm 5 times** and record the average execution time. - Record in a table for Word/Excel, and plot graphs. --- ## **Step 4: Present Results and Conclusion** - Put results in **Word/Excel** (tables, graphs) - Draw conclusions on performance vs. number type/implementation --- # **SOLUTION DETAILS** --- ## **A. C++ Code Example** ### **1. Data Generation** ```cpp #include <iostream> #include <vector> #include <random> #include <chrono> #define N 1000000 #define K 100 template<typename T> std::vector<T> generate_data(T min, T max) { std::vector<T> data(N); std::random_device rd; std::mt19937 gen(rd()); if constexpr (std::is_integral<T>::value) { std::uniform_int_distribution<T> dist(min, max); for (auto &x : data) x = dist(gen); } else { std::uniform_real_distribution<long double> dist(min, max); for (auto &x : data) x = static_cast<T>(dist(gen)); } return data; } ``` - Use `generate_data<int>(0, INT_MAX)` for int, etc. --- ### **2. Priority Queue with Array/Vector Heap** #### **a. Max Heap (array/vector)** ```cpp #include <queue> #include <functional> template<typename T> std::vector<T> find_k_smallest_array_heap(const std::vector<T>& data) { std::priority_queue<T> maxHeap; for (auto x : data) { if (maxHeap.size() < K) { maxHeap.push(x); } else if (x < maxHeap.top()) { maxHeap.pop(); maxHeap.push(x); } } std::vector<T> result; while (!maxHeap.empty()) { result.push_back(maxHeap.top()); maxHeap.pop(); } return result; // 100 smallest elements (unsorted) } ``` --- #### **b. Heap Using Binary Tree Node** You must **implement a binary heap tree** using nodes (not linked list, but as a tree structure). ```cpp template<typename T> struct Node { T val; Node* left; Node* right; Node* parent; Node(T v) : val(v), left(nullptr), right(nullptr), parent(nullptr) {} }; // Helper class for binary heap template<typename T> class BinaryHeapTree { Node<T>* root; int size; // Implement insert, delMax, swim, sink, etc. // Plus computeHeight, computeLeaves, lookup, sameLevel, descendant public: BinaryHeapTree() : root(nullptr), size(0) {} void insert(T val); T delMax(); // ... implement swim, sink, etc. int computeHeight(); int computeLeaves(); bool lookup(T key); std::vector<Node<T>*> sameLevel(Node<T>* current); bool descendant(Node<T>* current, Node<T>* aNode); // Add helpers for maintaining complete tree property // (such as storing pointers to all nodes in a vector for O(1) access) }; ``` *Implementing the full binary heap with all functions is lengthy; see [full code sample below](#full-code).* --- ### **3. Execution Time Measurement** ```cpp auto start = std::chrono::high_resolution_clock::now(); //... run function ... auto end = std::chrono::high_resolution_clock::now(); double elapsed = std::chrono::duration<double>(end - start).count(); ``` --- ### **4. Repeat for Each Data Type** Call `generate_data<T>()` and run both heap methods, measuring and recording execution time for each. --- ### **5. Example Table (Excel/Word format)** | Data Type | Heap (Vector) Avg Time (s) | Heap (Tree) Avg Time (s) | |---------------|---------------------------|--------------------------| | int | 0.12 | 0.68 | | long int | 0.13 | 0.70 | | long long int | 0.13 | 0.71 | | float | 0.12 | 0.69 | | double | 0.13 | 0.72 | | long double | 0.14 | 0.75 | (You’ll fill with your measured data.) --- ### **6. Example Graph** - X-axis: Data Type - Y-axis: Time (seconds) - Lines: Heap (Vector), Heap (Tree) --- ### **7. Conclusion Example** > **Conclusion:** > The array-based heap implementation is consistently faster than the binary tree heap for all data types, primarily due to better cache locality and simpler memory access patterns. The execution time increases slightly with larger data types (e.g., `long double`), but the trend is consistent. The binary tree heap, while functional, introduces significant overhead due to pointer manipulation and tree traversal. --- # **B. FULL SAMPLE CODE (Heap with Tree Node, Partial)** ```cpp // Only key methods shown for brevity template<typename T> class BinaryHeapTree { Node<T>* root; int size; std::vector<Node<T>*> nodes; // Maintain level order for insert/del public: BinaryHeapTree() : root(nullptr), size(0) {} void insert(T val) { Node<T>* node = new Node<T>(val); if (root == nullptr) { root = node; nodes.push_back(node); } else { // Insert at the end (maintain complete tree) Node<T>* parent = nodes[(size-1)/2]; if (!parent->left) parent->left = node; else parent->right = node; node->parent = parent; nodes.push_back(node); swim(size); } size++; } void swim(int idx) { while (idx > 0) { int parent = (idx-1)/2; if (nodes[parent]->val < nodes[idx]->val) { std::swap(nodes[parent]->val, nodes[idx]->val); idx = parent; } else break; } } T delMax() { if (size == 0) throw std::runtime_error("Empty heap"); T maxVal = root->val; // Move last node to root nodes[0]->val = nodes[size-1]->val; // Remove last node Node<T>* last = nodes.back(); if (last->parent) { if (last->parent->left == last) last->parent->left = nullptr; else last->parent->right = nullptr; } delete last; nodes.pop_back(); size--; sink(0); return maxVal; } void sink(int idx) { while (2*idx+1 < size) { int j = 2*idx+1; if (j+1 < size && nodes[j]->val < nodes[j+1]->val) j++; if (nodes[idx]->val >= nodes[j]->val) break; std::swap(nodes[idx]->val, nodes[j]->val); idx = j; } } // computeHeight: log2(size) int computeHeight() { return size==0 ? 0 : (int)std::ceil(std::log2(size+1)); } // computeLeaves: number of leaf nodes int computeLeaves() { return (size+1)/2; } // lookup: linear scan for simplicity bool lookup(T key) { for (auto node : nodes) if (node->val == key) return true; return false; } // sameLevel: return all nodes at same level as 'current' std::vector<Node<T>*> sameLevel(Node<T>* current) { int idx = -1; for (int i=0; i<nodes.size(); ++i) if (nodes[i]==current) idx = i; if (idx==-1) return {}; int level = (int)std::log2(idx+1); int start = (1<<level)-1, end = std::min((1<<(level+1))-2, size-1); std::vector<Node<T>*> res; for (int i=start; i<=end; ++i) res.push_back(nodes[i]); return res; } // descendant: check if aNode is below current bool descendant(Node<T>* current, Node<T>* aNode) { if (!current) return false; if (current == aNode) return false; if (current->left == aNode || current->right == aNode) return true; return descendant(current->left, aNode) || descendant(current->right, aNode); } }; ``` --- # **C. REPORT FORMAT (WORD/EXCEL)** --- ## 1. **Title Page** - Project Title: "Analysis of Priority Queue Implementations for Finding K Smallest Elements" - Your Name - Date --- ## 2. **Introduction** - Overview of problem, data sizes, and number types --- ## 3. **Methodology** - Data generation steps - Description of heap implementations - Description of timing methodology --- ## 4. **Results Table** | Data Type | Heap (Vector) Avg Time (s) | Heap (Tree) Avg Time (s) | |---------------|---------------------------|--------------------------| | int | | | | long int | | | | ... | | | --- ## 5. **Graphs** *(Paste Excel/Word bar or line graph)* --- ## 6. **Conclusion** - Summarize findings as in the sample above. --- ## 7. **Appendix** - Source code (C++), or link to GitHub repository --- --- # **Final Step-by-Step Answer** ### **Step 1**: Generate 1,000,000 random numbers for each data type. ### **Step 2**: For each data type, find 100 smallest using: - a) Max-heap (priority queue) with array/vector - b) Max-heap with binary tree of nodes (implement insert, delMax, swim, sink, height, leaves, lookup, sameLevel, descendant) ### **Step 3**: Time each run, repeat 5 times, record average. ### **Step 4**: Enter into table, plot graphs. ### **Step 5**: Write up findings, conclusion, and include code in appendix. --- **You can use the code above as a starting point, and fill in the rest as required. If you need the full code for all data types and a script for Excel automation, let me know!** --- **Final Answer:** *See solution steps above for code, report, and procedure. The implementation uses a max-heap (as priority queue) both with array/vector and binary tree, and measures their performance on different number types. Results are recorded in tables and graphs, showing that the array-based heap is more efficient for all tested data types.*