Heap sort

public void sort(int[] a) {
    buildMaxHeap(a);
    int size = a.length;
    for (int i = a.length - 1; i >= 1; i--) {
        int temp = a[0];
        a[0] = a[i]; a[i] = temp; size --; maxHeapify(a, i); }}Copy the code

An array stores the parent nodes of a binary tree

public int parent(int n) {
    return n >> 1;
}
Copy the code

The array stores the left child under the binary tree

public int left(int n) {
    return 2 * n + 1;
}
Copy the code

The array stores the right child under the binary tree

public int right(int n) {
    return 2 * n + 2;
}
Copy the code

Recursive implementation of big top heap

public void maxHeapify(int[] a, int n) {
    int l = left(n);
    int r = right(n);
    int largest;
    if (l <= a.length && a[l] > a[n]){
        largest = l;
    } else {
        largest = n;
    }
    if (r <= a.length && a[r] > a[largest]){
        largest = r;
    }
    if(largest ! = n) {inttemp = a[n]; a[n] = a[largest]; a[largest] = temp; maxHeapify(a, largest); }}Copy the code

Build the big top heap

public void buildMaxHeap(int[] a) {
    for (int i = a.length >> 1; i >= 0; i--) { maxHeapify(a, i); }}Copy the code

Recursive implementation of small top heap

public void minHeapify(int[] a, int n) {
    int l = left(n);
    int r = right(n);
    int mini;
    if (l <= a.length && a[l] < a[n]){
        mini = l;
    } else {
        mini = n;
    }
    if (r <= a.length && a[r] < a[mini]){
        mini = r;
    }
    if (mini != n) {
        int temp = a[n];
        a[n] = a[mini];
        a[mini] = temp;
        minHeapify(a, mini);
    }
}
Copy the code

Build the small top heap

public void buildMinHeap(int[] a) { for (int i = a.length >> 1; i >= 0; i--) { minHeapify(a, i); }}Copy the code