Hacktober-Accepted/heapsort.cpp at main · manjmauji/Hacktober-Accepted · 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
#include <iostream>
#include <cmath>
#include <vector>
class Stack
{
    public:
        int sizeOfHeap;
        std::vector <int> heapTab;


        void Kill()
        {

            Stack::~Stack;
        }

        void Heapify(int sizeOfHeap, int i)
        {
            int largest = i;
            int l = 2*i+1;
            int r = 2*i+2;

            if(l < sizeOfHeap && heapTab[l] > heapTab[largest]) largest = l;
            if(r < sizeOfHeap && heapTab[r] > heapTab[largest]) largest = r;
            if(largest != i)
            {
                std::swap(heapTab[i], heapTab[largest]);

                Heapify(sizeOfHeap,largest);
            }
        }

        void HeapSort()
        {
            for(int i = (sizeOfHeap /2) - 1; i>=0 ; i--)Heapify(sizeOfHeap,i);
            for(int i = sizeOfHeap - 1; i>=0 ; i--)
            {
                std::swap(heapTab[0],heapTab[i]);
                Heapify(i,0);
            }

        }


        void PrintHeap()
        {
            for(int i = 0 ;  i < sizeOfHeap ; ++i)std::cout<<heapTab[i]<<" ";
            std::cout<<std::endl;
        }

};


int main()
{
    Stack object;
    int choice;


    std::cout<< " podaj rozmiar drzewa binarnego" <<std::endl;
    std::cin>>object.sizeOfHeap;

    for(int i = 0 ; i < object.sizeOfHeap ; i++)
    {
        int value;
        std::cout<<"dodajesz " <<i+1<<"obiekt"<<std::endl;
        std::cin>>value;
        object.heapTab.push_back(value);
    }

    object.PrintHeap();
    std::cout<<"\n\n"<<std::endl;

    object.HeapSort();

    std::cout<<"sorted array"<<std::endl;
    object.PrintHeap();

    object.Kill();

    return 0;
}