Leetcode/Sort_an_Array.cpp at main · sazzadkhan20/Leetcode · 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
class Solution
{
public:
    vector<int> create_min_heap(vector<int> v)
    {
        vector<int> v1;
        for (int val : v)
        {
            v1.push_back(val);
            int cur = v1.size() - 1;
            while (cur > 0)
            {
                int parent = (cur - 1) / 2;
                if (v1[parent] > v1[cur])
                    swap(v1[parent], v1[cur]);
                else
                    break;
                cur = parent;
            }
        }
        return v1;
    }
    int delete_min_heap(vector<int> &v)
    {
        if (v.empty())
            return 0;
        int last_idx = v.size() - 1;
        int val = v[0];
        v[0] = v[last_idx];
        v.pop_back();
        int cur = 0;
        while (true)
        {
            int left = cur * 2 + 1;
            int right = cur * 2 + 2;
            if (left <= last_idx && right <= last_idx)
            {
                if (v[left] <= v[right] && v[left] < v[cur])
                {
                    swap(v[cur], v[left]);
                    cur = left;
                }
                else if (v[right] < v[left] && v[right] < v[cur])
                {
                    swap(v[cur], v[right]);
                    cur = right;
                }
                else
                {
                    break;
                }
            }
            else if (left <= last_idx)
            {
                if (v[left] < v[cur])
                {
                    swap(v[cur], v[left]);
                    cur = left;
                }
                else
                    break;
            }
            else if (right <= last_idx)
            {
                if (v[right] < v[cur])
                {
                    swap(v[cur], v[right]);
                    cur = right;
                }
                else
                    break;
            }
            else
            {
                break;
            }
        }
        return val;
    }
    vector<int> sortArray(vector<int> &v)
    {
        v = create_min_heap(v);
        int n = v.size();
        vector<int> v1;
        for (int i = 0; i < n; i++)
        {
            v1.push_back(delete_min_heap(v));
        }
        v = v1;
        v1.clear();
        return v;
    }
};