Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Lab2.cpp : This file contains the 'main' function. Program execution begins and ends there.
- //
- #include <iostream>
- #include "Profiler.h"
- #define SIZE 1000
- void heapfy(int a[],int i, int size_heap)
- {
- int left = 2 * i;
- int right = 2 * i + 1;
- int largest = i;
- if (left < size_heap && a[left] > a[largest])
- {
- largest = left;
- }
- if (right < size_heap && a[right] > a[largest])
- {
- largest = right;
- }
- if (i != largest)
- {
- std::swap(a[largest], a[i]);
- heapfy(a, largest, size_heap);
- }
- }
- void bubble_key(int a[], int pos, int key)
- {
- a[pos] = key;
- while (pos>1 && a[pos] > a[pos/2])
- {
- std::swap(a[pos], a[pos / 2]);
- pos = pos / 2;
- }
- }
- void insert_heap(int a[], int &size, int key)
- {
- size++;
- a[size] = INT_MIN;
- bubble_key(a, size, key);
- }
- // top down aproach
- void build_heap_td(int arr[], int size_arr)
- {
- int heap_size = 0;
- for (int i = 1; i < size_arr - 1;i++)
- {
- insert_heap(arr, heap_size, arr[i]);
- }
- }
- // bottom up aproach
- void build_heap_bu(int a[],int size)
- {
- for (int i = size/2; i > 0; i--)
- heapfy(a, i, size);
- }
- void print_arr(int arr[], int size)
- {
- for (int i = 1; i < size; i++)
- std::cout << arr[i] << " ";
- std::cout << "\n";
- }
- void heapsort(int a[],int size)
- {
- build_heap_td(a, size);
- print_arr(a, size);
- int end = size - 1;
- while (end > 1)
- {
- //print_arr(a, size);
- std::swap(a[end], a[1]);
- heapfy(a, 1, end);
- end--;
- }
- }
- void test_heapsort(int n)
- {
- int size = n+1;
- int *a= new int[size];
- FillRandomArray<int>(a, size, 0, 1000);
- heapsort(a, size);
- print_arr(a, size);
- delete[] a;
- }
- int main()
- {
- test_heapsort(10);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement