Can you help me with my programing homework in c++ for Heaps. More info in comments. Thanks

Posted by Erao_@reddit | learnprogramming | View on Reddit | 6 comments

I am stuck on how to make it that it doesent wait for 10000 elements and that it will sort even 2 for example also i still realy doesent understand heapsort and i heard that i could use swap so i would like to know what that is. thanks any help is realy appreciated.

Here are the original instructions:

Heap Sort (HeapSort)

Build a heap from the elements (N × adding an element to the heap) → time complexity O(N.log N), or bottom-up in linear time O(N)
Gradually dismantle the heap (N × removing the minimum from the heap) → time complexity O(N.log N)

→ total time complexity O(N.log N) even in the worst case

Sorts in-place (doesn't need an extra data structure of size N):

elements stored in the array are gradually inserted into the heap, which is built in the left part of the same array
then the heap is gradually dismantled and the removed elements are stored from the back into the right part of the same array, where space is freed as the heap shrinks

Your Task:

You have basic knowledge of the heap data structure and the HeapSort algorithm. Your task is to implement a sort method for an array of the record structure defined below. The sorting algorithm must work in-place. You don't need to worry about time complexity.

Your submission must include:

A program with a sort method that takes an input array of record elements and sorts them from oldest to newest (by addTime). Elements are read from standard input. Assume a maximum array size of 10 000. The program should also print the sorted array.

Structure record:

Members:

string id
unsigned int addTime (representing a unix timestamp)
char category

Here is the input:

66a82653-e164-4c67-89a7-1a266b82b2f0 1209807225 E

175c09e6-7776-4a45-a7f1-5e4a27282e38 724367075 D

// du upg 2.cpp : This file contains the 'main' function. Program execution begins and ends the #include <iostream> using namespace std; struct zaznamu { char kategorie; unsigned int addTime; string id; }; void heapify(zaznamu arr[], int n, int i) { int max = i; int lev = 2 * i + 1; int prav = 2 * i + 2; if (lev < n && arr[lev].addTime > arr[max].addTime) max = lev; if (prav < n && arr[prav].addTime > arr[max].addTime) max = prav; if (max != i) { swap( arr[i], arr[max] ); heapify ( arr, n, max ); } } void heapsort(zaznamu arr[], int n) { for (int a = n / 2 - 1; a >= 0; a--) { heapify(arr, n, a); } for (int b = n - 1; b > 0; b--) { swap( arr[0], arr[b]); heapify( arr, b, 0); } } int main() { const int max = 10000; zaznamu arr[max]; int c = 0; while (c < max && cin >> arr[c].id >> arr[c].addTime >> arr[c].kategorie) { c++; } heapsort(arr, c); for (int d = 0; d < c; d++) { cout << arr[d].id << " " << arr[d].addTime << " " << arr[d].kategorie << endl; } return 0; }

[-]

Status-Sweet-9229@reddit

your code probably has a fixed array size of 10000 and you're reading exactly that many elements. you need to read the first number (2 in your example) which tells you how many records follow, then only process that amount.

for the swap function, it's just switching two elements in array - something like `temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;` but c++ has built-in `std::swap(arr[i], arr[j])` which does same thing.

Erao_@reddit (OP)

if it helps here is my code

I am stuck on how to make it that it doesent wait for 10000 elements Here is the input: 2

The input tells you how many elements there are going to be. So you need a loop to count up to that number, asking for the elements.