# DSL_Assignment11

Pratham16
c_cpp
2 years ago
2.7 kB
218
Indexable
Never
```//Heap sort algorithm
//Pratham Doke
#include <iostream>
#include <math.h>

using namespace std;

class MinHeap
{
int *harr;     // pointer to array of elements in heap
int capacity;  // maximum possible size of min heap
int heap_size; // Current number of elements in min heap
public:
MinHeap(int cap)
{
heap_size = cap;
capacity = cap;
harr = new int[cap];
}

void printArray()
{
for (int i = 0; i < heap_size; i++)
cout << harr[i] << " ";
cout << endl;
}

int parent(int i)
{
return (i - 1) / 2;
}

int left(int i)
{
return (2 * i + 1);
}

int right(int i)
{
return (2 * i + 2);
}
int getMin()
{
return harr[0];
}
void MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(harr[i], harr[smallest]);
MinHeapify(smallest);
}
}
// Method to remove minimum element (or root) from min heap
int extractMin()
{
if (heap_size <= 0)
return 999999;
if (heap_size == 1)
{
heap_size--;
return harr[0];
}

// Store the minimum value, and remove it from heap
int root = harr[0];
harr[0] = harr[heap_size - 1];
heap_size--;
MinHeapify(0);
// printArray();
// cout <<"--"<<harr[0]<<"--";
return root;
}

void getUnsortedArray()
{
cout << "Enter " << capacity << " no of elements to sort using HEAPSORT" << endl;
for (int i = 0; i < capacity; i++)
cin >> harr[i];
}

void heapSort()
{
int temp[capacity];
for (int j = 0; j < capacity; j++)
{
// cout<<extractMin()<<" ";
temp[j] = extractMin();
cout << temp[j] << " ";
}
}
};

int main()
{
int s;
cout << "Enter Size of Min Heap" << endl;
cin >> s; // 5
MinHeap obj(s);
obj.getUnsortedArray(); // 7 4 3 9 8

cout << "Unsorted Array :" << endl;
obj.printArray();

for (int i = s / 2 - 1; i >= 0; i--)
{
obj.MinHeapify(i);
}

// cout << "Heapified Array :"<<endl;
// obj.printArray();

cout << "Heap Sorted Array :" << endl;
obj.heapSort();
}```