cpp-practice/heap.cpp at main · jitaditya004/cpp-practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
using namespace std;

class HeapSort {
    int *arr;
    int size;

public:
    HeapSort(int n) {
        size = n;
        arr = new int[size];
    }

    void inputArray() {
        cout << "Enter " << size << " elements: ";
        for (int i = 0; i < size; i++) {
            cin >> arr[i];
        }
    }

   /* void heapify(int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest])
            largest = left;

        if (right < n && arr[right] > arr[largest])
            largest = right;

        if (largest != i) {
            swap(arr[i], arr[largest]);
            heapify(n, largest);
        }
    }

    void heapSort() {
        for (int i = size / 2 - 1; i >= 0; i--) {
            heapify(size, i);
        }

        for (int i = size - 1; i > 0; i--) {
            swap(arr[0], arr[i]);
            heapify(i, 0);
        }
    }
   */
    void printArray() {
        cout << "Sorted array: ";
        for (int i = 0; i < size; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }

    ~HeapSort() {
        delete[] arr;
    }


    void heapify(int n,int i){
          int large=i;
          int left=2*i+1;
          int right=2*i+2;

          if(left<n && arr[left] > arr[large])  large=left;
          if(right<n && arr[right] > arr[large]) large=right;

          if(large != i){
              swap(arr[i],arr[large]);
              heapify(n,large);
          }
     }


     void heapSort(){
          for(int i=size/2 -1;i>=0;i--){
              heapify(size,i);
          }
          for(int i=size-1;i>0;i--){
              swap(arr[i],arr[0]);
              heapify(i,0);
            }

      }


};

int main() {
    int n;
    cout << "Enter number of elements: ";
    cin >> n;
    HeapSort hs(n);
    hs.inputArray();
    hs.heapSort();
    hs.printArray();
    return 0;
}


//his program sorts an array using Heap Sort. It constructs a max heap, then repeatedly extracts the maximum element to sort the array. Let me know if you need modifications!