class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        auto heapify = [&](int i, int e) {
            while (i <= e) {
                int left = 2 * i + 1;
                int right = 2 * i + 2;

                int j = i;

                if (left <= e && nums[left] > nums[j]) {
                    j = left;
                };
                if (right <= e && nums[right] > nums[j]) {
                    j = right;
                };

                if (j == i) {
                    break;
                };

                swap(nums[i], nums[j]);
                swap(i, j);
            }
        };
        
        const int length = nums.size();
        
        // initialize heap
        for (int i = length / 2; i >= 0; i--) {
            heapify(i, length - 1);
        }
        
        // get mininimum
        for (int i = length - 1; i >= 1; i--) {
            swap(nums[0], nums[i]);
            heapify(0, i - 1);    
        }
        
        return nums;
    }
};