Heap sort instance of Java array implementation
- 2020-12-10 00:41:28
- OfStack
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
}
}