How to implement heap sort algorithm using java

How to use Java to implement the heap sort algorithm

Heap sort is a sorting algorithm based on the heap data structure, which takes advantage of the properties of the heap for sorting. Heap sort is divided into two main steps: building the heap and sorting.

Building a heap:
First, we need to build a large root heap or a small root heap based on the array to be sorted. For ascending sort, we need to build a large root heap; for descending sort, we need to build a small root heap.

The property of a large root heap is: the value of a node is greater than or equal to the value of its child nodes.
The properties of the small root heap are: the value of a node is less than or equal to the value of its child nodes.

The process of building a large root heap is as follows:

public static void buildHeap(int[] array, int length) {
    for (int i = length / 2 - 1; i >= 0; i--) {
        heapify(array, length, i);
    }
}

public static void heapify(int[] array, int length, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < length && array[left] > array[largest]) {
        largest = left;
    }

    if (right < length && array[right] > array[largest]) {
        largest = right;
    }

    if (largest != i) {
        int temp = array[i];
        array[i] = array[largest];
        array[largest] = temp;
        heapify(array, length, largest);
    }
}

Sort:
After building the large root heap, we need to exchange the top element of the heap with the last element of the array, and shrink the heap range, and then heapize the heap again, repeating this process until the heap is empty. The final array is ordered.

public static void heapSort(int[] array) {
    int length = array.length;

    buildHeap(array, length);

    for (int i = length - 1; i >= 0; i--) {
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;

        heapify(array, i, 0);
    }
}

Usage example:

public static void main(String[] args) {
    int[] array = {4, 10, 3, 5, 1};
    heapSort(array);

    System.out.println(Arrays.toString(array));
}

The output result is: [1, 3, 4, 5, 10], which is the result of ascending order.

The time complexity of heap sorting is O(nlogn), where n is the number of elements to be sorted. Heap sort is a stable sorting algorithm suitable for sorting large-scale data.

The above is the detailed content of How to implement heap sort algorithm using java. For more information, please follow other related articles on the PHP Chinese website!