Untitled
unknown
plain_text
2 years ago
2.6 kB
2
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(); }\