Using C Create a sorting algorithm based on Heap Your sortin

Using C++

Create a sorting algorithm based on Heap. Your sorting algorithm has to be contained in a function:

void HeapSort(vector &v){

}

The function takes v as a parameter and sorts it by

Step 1: sequentially adding elements from v into heap

Step 2: extracting elements from the heap back into v

Demonstrate the work of your program on a test example.

Please help using this program with the function:

#include

#include

#include

using namespace std;

void swap(int &x, int &y){

int temp = x; x = y; y = temp;

}

class Heap{

private:

vector _data;

public:

void Insert(int A){

_data.push_back(A);

BubbleUp(_data.size()-1);

}

int Size(){return _data.size();}

int Top(){return _data[0];}

void BubbleUp(int ind){

if(ind == 0) return; // step 0;

if(_data[ind] < _data[ind/2]){

swap(_data[ind], _data[ind/2]);

BubbleUp(ind/2);

}

}

int Extract(){

if(_data.size() == 0) return -1;

int ret = _data[0];

_data[0] = _data[_data.size()-1];

_data.pop_back();

BubbleDown(0);

return ret;

}

void BubbleDown(int ind){

if((ind*2) >= (_data.size()-1)) return; // no children, just exit

if((ind*2) == (_data.size()-1) && _data[ind*2] < _data[ind]){ // only one child: check, swap if needed return.

swap(_data[ind*2], _data[ind]);

return;

}

if(_data[ind*2] < _data[ind] || _data[ind*2+1] < _data[ind]){ // there is a heap violation...

if(_data[ind*2] < _data[ind*2+1]){ // left child is less than the right child...

swap(_data[ind*2], _data[ind]); // swap the left and the parent

BubbleDown(ind*2); // this will take care of the rest

}

else{ // right child < left child

swap(_data[ind*2+1], _data[ind]); // swap the right and the parent

BubbleDown(ind*2+1); // this will take care of the rest

}

}

}

void Print(){

for(int a: _data){

cout << a << \"\\t\";

}

cout << endl;

}

};

int KthMinElement(const vector &v, int k){

Heap theBob;

for(int x : v)

theBob.Insert(x);

int ret;

for(int i = 0; i < k; i++)

ret = theBob.Extract();

return ret;

}

int KthMaxElement(const vector &v, int k){

Heap h;

// we have to keep adding elements to the heap while:

// (1) the size of the heap is less than k

// (2) if the element at the top of the heap is less than x

// After adding an element, if the size of the heap is greater than k, then extract one element

// At the end of the procedure, the kth max element is at the top of the heap

for(int x: v){

if(h.Size() < k || h.Top() < x){

h.Insert(x);

if(h.Size() > k){

h.Extract();

}

}

}

return h.Extract();

}

int main()

{

vector X;

for(int i = 0; i < 10; i++){

X.push_back(i+1);

}

int k = 3;

cout << k << \"th min element: \" << KthMinElement(X, k) << endl;

}

Solution

#include <iostream>

using namespace std;

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap

void heapify(int arr[], int n, int i)

{

    int largest = i; // Initialize largest as root

    int l = 2*i + 1; // left = 2*i + 1

    int r = 2*i + 2; // right = 2*i + 2

    // If left child is larger than root

    if (l < n && arr[l] > arr[largest])

        largest = l;

    // If right child is larger than largest so far

    if (r < n && arr[r] > arr[largest])

        largest = r;

    // If largest is not root

    if (largest != i)

    {

        swap(arr[i], arr[largest]);

        // Recursively heapify the affected sub-tree

        heapify(arr, n, largest);

    }

}

// main function to do heap sort

void heapSort(int arr[], int n)

{

    // Build heap (rearrange array)

    for (int i = n / 2 - 1; i >= 0; i--)

        heapify(arr, n, i);

    // One by one extract an element from heap

    for (int i=n-1; i>=0; i--)

    {

        // Move current root to end

        swap(arr[0], arr[i]);

        // call max heapify on the reduced heap

        heapify(arr, i, 0);

    }

}

/* A utility function to print array of size n */

void printArray(int arr[], int n)

{

    for (int i=0; i<n; ++i)

        cout << arr[i] << \" \";

    cout << \"\ \";

}

// Driver program

int main()

{

    int arr[] = {12, 11, 13, 5, 6, 7};

    int n = sizeof(arr)/sizeof(arr[0]);

    heapSort(arr, n);

    cout << \"Sorted array is \ \";

    printArray(arr, n);

}