Heap sort instance of Java array implementation

Heap sorting: Utilizes the large root heap

The array is piled up, and then the heap is piled up and inserted back into the array, and the array is ordered from small to large.

public class MaxHeap<T extends Comparable<? super T>> {
 private T[] data;
 private int size;
 private int capacity;
 
 public MaxHeap(int capacity) {
  this.data = (T[]) new Comparable[capacity + 1];
  size = 0;
  this.capacity = capacity;
 }
 
 public int size() {
  return this.size;
 }
 
 public boolean isEmpty() {
  return size == 0;
 }
 
 public int getCapacity() {
  return this.capacity;
 }
 
 /**
  * @return  View the maximum root ( Can't delete ,  with popMax contrast )
  */
 public T seekMax() {
  return data[1];
 }
 
 public void swap(int i, int j) {
  if (i != j) {
   T temp = data[i];
   data[i] = data[j];
   data[j] = temp;
  }
 }
 
 public void insert(T item) {
  size++;
  data[size] = item;
  shiftUp(size);
 }
 
 /**
  * @return  Maximum pop root ( Pop up means delete ,  with seekMax contrast )
  */
 public T popMax() {
  swap(1, size--);
  shiftDown(1);
  return data[size + 1];
 }
 
 /**
  * @param child  The child node subscript is child , the parent node is the lower corner table child/2
  */
 public void shiftUp(int child) {
  while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {
   swap(child, child / 2);
   child = child / 2;
  }
 }
 
 /**
  * @param a data The subscript of an element in an array 
  * @param b data The subscript of an element in an array 
  * @return  Returns the subscript of which element is larger 
  */
 private int max(int a, int b) {
  if (data[a].compareTo(data[b]) < 0) {// if data[b] big 
   return b;// return b
  } else {// if data[a] big 
   return a;// return a
  }
 }
 
 /**
  * @param a data The subscript of an element in an array 
  * @param b data The subscript of an element in an array 
  * @param c data The subscript of an element in an array 
  * @return  Returns the subscript of which element is larger 
  */
 private int max(int a, int b, int c) {
  int biggest = max(a, b);
  biggest = max(biggest, c);
  return biggest;
 }
 
 
 /**
  * @param father  The parent node subscript is father, The lower corner table of the left and right child nodes is as follows: father*2  and  father*2+1
  */
 public void shiftDown(int father) {
  while (true) {
   int lchild = father * 2;// Left the child 
   int rchild = father * 2 + 1;// The right child 
   int newFather = father;//newFather About to update, father, left, right 3 Which node is bigger, newFather Whose subscript 
 
   if (lchild > size) {// If the father The node has neither left nor right children 
    return;
   } else if (rchild > size) {// If the father Nodes have only left children, no right children 
    newFather = max(father, lchild);
   } else {// If the father The node has both left children and right children 
    newFather = max(father, lchild, rchild);
   }
 
   if (newFather == father) {// instructions father It's bigger than the two children, and the table name is already a big root heap, so you don't have to adjust it any more 
    return;
   } else {// Otherwise, you need to continue tuning the heap until the large root heap condition is satisfied 
    swap(father, newFather);// Exchange values 
    father = newFather;// update father Is equivalent to continuing to adjust shiftDown(newFather)
   }
  }
 }
 
 public static <T extends Comparable<? super T>> void sort(T[] arr) {
  int len = arr.length;
  // Into the heap 
  MaxHeap<T> maxHeap = new MaxHeap<T>(len);
  for (int i = 0; i < len; i++) {
   maxHeap.insert(arr[i]);
  }
  // Out of the heap 
  for (int i = len - 1; i >= 0; i--) {
   arr[i] = maxHeap.popMax();
  }
 }
 
 public static void printArr(Object[] arr) {
  for (Object o : arr) {
   System.out.print(o);
   System.out.print("\t");
  }
  System.out.println();
 }
 
 public static void main(String args[]) {
  Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  printArr(arr);//3 5 1 7 2 9 8 0 4 6
  sort(arr);
  printArr(arr);//0 1 2 3 4 5 6 7 8 9
 }
}

Heap sort: Construct a heap (maximum heap) on an array

public class MaxHeap<T extends Comparable<? super T>> {
 private T[] data;
 private int size;
 private int capacity;
 
 public MaxHeap(int capacity) {
  this.capacity = capacity;
  this.size = 0;
  this.data = (T[]) new Comparable[capacity + 1];
 }
 
 public MaxHeap(T[] arr) {//heapify, Number to form a heap 
  capacity = arr.length;
  data = (T[]) new Comparable[capacity + 1];
  System.arraycopy(arr, 0, data, 1, arr.length);
  size = arr.length;
  for (int i = size / 2; i >= 1; i--) {
   shiftDown(i);
  }
 }
 
 public int size() {
  return this.size;
 }
 
 public int getCapacity() {
  return this.capacity;
 }
 
 public boolean isEmpty() {
  return size == 0;
 }
 
 public T seekMax() {
  return data[1];
 }
 
 public void swap(int i, int j) {
  if (i != j) {
   T temp = data[i];
   data[i] = data[j];
   data[j] = temp;
  }
 }
 
 public void insert(T item) {
  size++;
  data[size] = item;
  shiftUp(size);
 }
 
 public T popMax() {
  swap(1, size--);
  shiftDown(1);
  return data[size + 1];
 }
 
 public void shiftUp(int child) {
  while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {
   swap(child, child / 2);
   child /= 2;
  }
 }
 
 /**
  * @param a data The subscript of an element in an array 
  * @param b data The subscript of an element in an array 
  * @return  Returns the subscript of which element is larger 
  */
 private int max(int a, int b) {
  if (data[a].compareTo(data[b]) < 0) {// if data[b] big 
   return b;// return b
  } else {// if data[a] big 
   return a;// return a
  }
 }
 
 /**
  * @param a data The subscript of an element in an array 
  * @param b data The subscript of an element in an array 
  * @param c data The subscript of an element in an array 
  * @return  Returns the subscript of which element is larger 
  */
 private int max(int a, int b, int c) {
  int biggest = max(a, b);
  biggest = max(biggest, c);
  return biggest;
 }
 
 public void shiftDown(int father) {
  while (true) {
   int lchild = father * 2;
   int rchild = father * 2 + 1;
   int newFather = father;// It doesn't matter if I assign a value here, if I take this one down here return to break, Then you have to assign something 
 
   if (lchild > size) {// If there are no left or right children 
    return;
   } else if (rchild > size) {// If there is no right child 
    newFather = max(father, lchild);
   } else {// If there are left and right children 
    newFather = max(father, lchild, rchild);
   }
 
   if (newFather == father) {// If the original parent is 3 The largest, then do not continue to sort the heap 
    return;
   } else {// If the parent node is not the largest, the large child is swapped up, and the heap continues to adjust down until the large root heap is satisfied 
    swap(newFather, father);
    father = newFather;// Equivalent to continuing shiftDown(newFather) . if newFather Turned out to be father Left child, that's equivalent to shiftDown(2*father)
   }
  }
 }
 
 public static <T extends Comparable<? super T>> void sort(T[] arr) {
  int len = arr.length;
  MaxHeap<T> maxHeap = new MaxHeap<>(arr);
  for (int i = len - 1; i >= 0; i--) {
   arr[i] = maxHeap.popMax();
  }
 }
 
 public static void printArr(Object[] arr) {
  for (Object o : arr) {
   System.out.print(o);
   System.out.print("\t");
  }
  System.out.println();
 }
 
 public static void main(String args[]) {
  Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  printArr(arr);//3 5 1 7 2 9 8 0 4 6
  sort(arr);
  printArr(arr);//0 1 2 3 4 5 6 7 8 9
 }
}