1
class Solution {
2

3
  public void downHeapify(int[] nums, int startIndex, int lastIndex) {
4

5
    int parentIndex = startIndex;
6
    int leftChildIndex = 2 * parentIndex + 1;
7
    int rightChildIndex = 2 * parentIndex + 2;
8

9
    while (leftChildIndex <= lastIndex) {
10
      int maxIndex = parentIndex;
11
      if (nums[leftChildIndex] > nums[maxIndex]) {
12
        maxIndex = leftChildIndex;
13
      }
14
      if (rightChildIndex <= lastIndex && nums[rightChildIndex] > nums[maxIndex]) {
15
        maxIndex = rightChildIndex;
16
      }
17
      if (maxIndex == parentIndex) {
18
        return;
19
      }
20
      int temp = nums[maxIndex];
21
      nums[maxIndex] = nums[parentIndex];
22
      nums[parentIndex] = temp;
23
      parentIndex = maxIndex;
24
      leftChildIndex = 2 * parentIndex + 1;
25
      rightChildIndex = 2 * parentIndex + 2;
26
    }
27
    return;
28
  }
29

30
  public int[] sortArray(int[] nums) {
31
    int len = nums.length;
32
    // building a heap - O(n) time
33
    for (int i = (len / 2) - 1; i >= 0; i--) {
34
      downHeapify(nums, i, len - 1);
35
    }
36
    // sorting element - nlogn(n) time
37
    for (int i = len - 1; i > 0; i--) {
38
      int temp = nums[i];
39
      nums[i] = nums[0];
40
      nums[0] = temp;
41
      downHeapify(nums, 0, i - 1);
42
    }
43
    return nums;
44
  }
45
}