SHARE
TWEET

Untitled

a guest Oct 21st, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Lab2.cpp : This file contains the 'main' function. Program execution begins and ends there.
  2. //
  3.  
  4. #include <iostream>
  5. #include "Profiler.h"
  6.  
  7. #define SIZE 1000
  8.  
  9. void heapfy(int a[],int i, int size_heap)
  10. {
  11.     int left = 2 * i;
  12.     int right = 2 * i + 1;
  13.     int largest = i;
  14.     if (left < size_heap && a[left] > a[largest])
  15.     {
  16.         largest = left;
  17.     }
  18.    
  19.     if (right < size_heap && a[right] > a[largest])
  20.     {
  21.         largest = right;
  22.     }
  23.     if (i != largest)
  24.     {
  25.         std::swap(a[largest], a[i]);
  26.         heapfy(a, largest, size_heap);
  27.     }
  28. }
  29.  
  30. void bubble_key(int a[], int pos, int key)
  31. {
  32.  
  33.     a[pos] = key;
  34.  
  35.     while (pos>1 && a[pos] > a[pos/2])
  36.     {
  37.         std::swap(a[pos], a[pos / 2]);
  38.         pos = pos / 2;
  39.     }
  40.  
  41. }
  42.  
  43. void insert_heap(int a[], int &size, int key)
  44. {
  45.     size++;
  46.     a[size] = INT_MIN;
  47.     bubble_key(a, size, key);
  48. }
  49. // top down aproach
  50. void build_heap_td(int arr[], int size_arr)
  51. {
  52.     int heap_size = 0;
  53.     for (int i = 1; i < size_arr - 1;i++)
  54.     {
  55.        
  56.         insert_heap(arr, heap_size, arr[i]);
  57.     }
  58.    
  59. }
  60. // bottom up aproach
  61. void build_heap_bu(int a[],int size)
  62. {
  63.     for (int i = size/2; i > 0; i--)
  64.         heapfy(a, i, size);
  65.  
  66. }
  67.  
  68. void print_arr(int arr[], int size)
  69. {
  70.     for (int i = 1; i < size; i++)
  71.         std::cout << arr[i] << " ";
  72.     std::cout << "\n";
  73. }
  74.  
  75. void heapsort(int a[],int size)
  76. {
  77.     build_heap_td(a, size);
  78.     print_arr(a, size);
  79.     int end = size - 1;
  80.     while (end > 1)
  81.     {  
  82.         //print_arr(a, size);
  83.         std::swap(a[end], a[1]);
  84.         heapfy(a, 1, end);
  85.         end--;
  86.     }
  87. }
  88.  
  89. void test_heapsort(int n)
  90. {
  91.     int size = n+1;
  92.     int *a= new int[size];
  93.  
  94.     FillRandomArray<int>(a, size, 0, 1000);
  95.    
  96.     heapsort(a, size);
  97.     print_arr(a, size);
  98.  
  99.     delete[] a;
  100. }
  101.  
  102. int main()
  103. {
  104.     test_heapsort(10);
  105.    
  106. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top