Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- For the two ways of building the heap from an unordered array, we can conclude that the Bottom-Up approach is faster.
- This happens because in the case of the Top-Down approach, the Heapify function is called on all the nodes, after the unordered heap was built.
- In the Bottom-Up approach, the algorithm assumes that the leaves are already in place, so it only applies to n/2 nodes.
- running times: -Bottom-up : O(n);
- -Top-down : O(nlog(n));
- */
- #ifdef _MSC_VER
- #define _CRT_SECURE_NO_WARNINGS
- #endif
- #include <iostream>
- #include <fstream>
- #include <stdlib.h>
- #include <time.h>
- #define arr_size 10
- #define max 5000
- using namespace std;
- int counterCB = 0;
- int counterAB = 0;
- //Bottom-Up
- void Bottom_UP(int arr[], int n, int i)
- {
- int largest = i; //init the target as root
- int l = 2 * i + 1;
- int r = 2 * i + 2;
- counterCB++;
- if (l < n && arr[l] > arr[largest])
- largest = l;
- counterCB++;
- if (r < n && arr[r] > arr[largest])
- largest = r;
- if (largest != i)
- {
- swap(arr[i], arr[largest]);
- counterAB = counterAB + 3;
- Bottom_UP(arr, n, largest);
- }
- }
- void buildHeapBU(int arr[], int n)
- {
- for (int i = (n / 2) - 1; i >= 0; i--)
- Bottom_UP(arr, n, i);
- }
- void sort(int arr[], int n)
- {
- buildHeapBU(arr, n);
- //one by one extract elements from the heap
- for (int i = n - 1; i >= 1; i--)
- {
- //move current root to end
- swap(arr[0], arr[i]);
- Bottom_UP(arr, i, 0);
- }
- }
- void print_array(int arr[], int n)
- {
- for (int i = 0; i < n; i++)
- cout << arr[i] << " ";
- cout << endl;
- }
- // Top-Down
- int ReturnParent(int index)
- {
- return (index - 1) / 2;
- }
- int counterAT = 0;
- int counterCT = 0;
- void Key(int arr[], int index)
- {
- while (index > 0 && arr[ReturnParent(index)] < arr[index])
- {
- counterCT++;
- counterAT = counterAT + 3;
- swap(arr[index], arr[ReturnParent(index)]);
- index = ReturnParent(index);
- }
- }
- void HeapInsert(int arr[], int &size)
- {
- Key(arr, size);
- size++;
- }
- void buildHeap(int arr[], int n)
- {
- int size = 1;
- for (int i = 1; i <= n; i++)
- HeapInsert(arr, size);
- }
- int main()
- {
- int arr1[arr_size], arr2[arr_size];
- srand((unsigned int)time(NULL));
- //proof of correctness
- for (int i = 0; i < arr_size; i++)
- {
- arr1[i] = rand() % 1001;
- arr2[i] = arr1[i];
- }
- //proof of correctness for Top-Down
- cout << " Top-Down: " << endl;
- cout << endl;
- cout << " The initial array is: " << endl;
- print_array(arr1, arr_size);
- buildHeap(arr1, arr_size);
- cout << " The heap is: " << endl;
- print_array(arr1, arr_size);
- cout << endl;
- //proof of correctness for Bottom-Up
- cout << " Bottom-Up:" << endl;
- cout << endl;
- cout << " The array is: \n";
- print_array(arr2, arr_size);
- cout << " The unsorted heap is: \n";
- buildHeapBU(arr2, arr_size);
- print_array(arr2, arr_size);
- cout << " The sorted heap is: \n";
- sort(arr2, arr_size);
- print_array(arr2, arr_size);
- // average
- ofstream MyFile1;
- MyFile1.open("MyFile1.csv");
- MyFile1 << "n,Bottom A Average,Bottom C Average ,Bottom T Average,Top A Average,Top C Average,Top T Average " << "\n";
- int arr3[max],arr4[max];
- for (int n = 200; n <= 5000; n = n + 200)
- {
- counterAB = 0;
- counterCB = 0;
- counterAT = 0;
- counterCT = 0;
- for (int m = 0; m < 5; m++)
- {
- for (int i = 0; i < n; i++) {
- arr3[i] = rand() % max;
- arr4[i] = arr3[i];
- }
- buildHeapBU(arr3, n);
- buildHeap(arr4, n);
- }
- counterAB = counterAB / 5;
- counterCB = counterCB / 5;
- counterAT = counterAT / 5;
- counterCT = counterCT / 5;
- MyFile1 << n << "," << counterAB << "," << counterCB << "," << counterAB + counterCB << "," << counterAT << "," << counterCT << "," << counterAT + counterCT << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement