introduction
Heap Sort is a sorting algorithm based on heap data structure. Heap is a special completely binary tree. Heap sort uses the properties of the heap to arrange array elements in ascending or descending order through a series of operations. The time complexity of heap sorting is O(n log n), which is an unstable sorting algorithm and its spatial complexity is O(1), so it is very useful in some scenarios.
1. The basic principles of heap sorting
The core of heap sort is the data structure of heap (Heap). Heap has two forms:
(1) Max-Heap:The value of each node is greater than or equal to the value of its child node, and the value of the root node is the maximum value of the entire heap.
(2) Minimum heap (Min-Heap):The value of each node is less than or equal to the value of its child node, and the value of the root node is the minimum value of the entire heap.
Heap sorting generally uses the largest heap to sort arrays. The heap sorting process can be divided into two main steps:
(1) Build the largest heap:Convert an unordered array to a maximum heap.
(2) Sorting process:Repeat the heap top element (maximum value) with the last element of the current heap, and adjust the heap until only one element is left in the heap.
2. Implementation steps of heap sorting
(1) Build the largest heap:First, the input unordered array is constructed into the maximum heap. At this time the largest element in the array is located at the root node.
(2) Exchange the top element of the heap and the last element:Exchange the top element of the heap with the last element of the heap and reduce the number of effective elements of the heap.
(3) Heavy:Compare the root node with its child nodes and adjust the structure of the heap to resatisfie the properties of the largest heap.
(4) Repeat steps 2 and 3:Until the number of valid elements of the heap is 1, the entire array has been sorted.
3. Time complexity and spatial complexity of heap sorting
(1) Time complexity:The time complexity of building the largest heap is O(n), while the time complexity of each heap is O(log n), so the total time complexity is O(n log n).
(2) Space complexity:Heap sorting is an in-situ sorting algorithm, so its spatial complexity is O(1). 4. Java implementation of heap sorting
Here is the Java implementation code for heap sorting:
public class HeapSort {
// Heaping process ensures that the subtree with i as the root meets the properties of the heap private static void heapify(int[] arr, int n, int i) {
int largest = i; // Initialize the maximum value to the root node int left = 2 * i + 1; // The position of the left child node int right = 2 * i + 2; // The location of the right child node
// If the left child node is larger than the root node if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If the right child node is greater than the current maximum value if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If the maximum value is not the root node, exchange and continue to heap if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Recursively heap the affected subtree heapify(arr, n, largest);
}
}
// Heap sorting main function public static void heapSort(int[] arr) {
int n = ;
// Build the largest heap for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Gradually exchange the top element of the heap with the last element and adjust the heap for (int i = n - 1; i >= 1; i--) {
// Exchange the heap top element with the last element of the currently unsorted part int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Adjust the heap heapify(arr, i, 0);
}
}
// Print array private static void printArray(int[] arr) {
for (int i = 0; i < ; i++) {
(arr[i] + " ");
}
();
}
public static void main(String[] args) {
int[] arr = {4, 10, 3, 5, 1};
("Original array:");
printArray(arr);
heapSort(arr);
("Sorted array:");
printArray(arr);
}
}4. Heap sorting workflow
Let's understand the workflow of heap sorting with a simple example.
1. Build the largest heap
Suppose we have an array arr = [4, 10, 3, 5, 1].
(1) Initial array: [4, 10, 3, 5, 1]
(2) In the process of building the largest heap, we start with i = n/2 - 1 and adjust each node in turn until the root node.
(3) Adjusted heap: [10, 5, 3, 4, 1], the element at the top of the heap is the maximum value.
2. Sorting process
Swap the heap top element with the last element and adjust the heap.
(1) First exchange:After swapping the heap top and the last element, the array becomes: [1, 5, 3, 4, 10]. Then heap the remaining elements, and the adjusted heap is: [5, 4, 3, 1, 10].
(2) Second exchange:Swap the top and penultimate elements of the heap, and the array becomes: [1, 4, 3, 5, 10], and the adjusted heap is: [4, 1, 3, 5, 10].
(3) The third exchange:Swap the top and the penultimate element of the heap, the array becomes: [3, 1, 4, 5, 10], and the adjusted heap is: [3, 1, 4, 5, 10].
(4) The fourth exchange:Swap the top of the heap and the fourth last element, and the array becomes: [1, 3, 4, 5, 10]. At this time, there is only one element left and the sorting is completed.
Finally, the array becomes an ascending order: [1, 3, 4, 5, 10].
5. Pros and cons of heap sorting
advantage:
(1) Time complexity is stable:Regardless of the input data, the time complexity of heap sort is always O(n log n) and is not affected by the data distribution.
(2) Low space complexity:Heap sorting is an in-situ sorting algorithm with a spatial complexity of O(1) without additional auxiliary space.
(3) Suitable for big data processing:Since the time complexity of heap sorting is stable and does not depend on the initial state of the data, it is suitable for sorting large data volumes.
shortcoming:
(1) Not stable sorting:Heap sorting does not guarantee the relative order of equal elements, so it is not suitable for scenarios where stable sorting is required.
(2) The constant factors are relatively large:Although the time complexity of heap sort is O(n log n), its constant factor is relatively large, which is usually slower than fast sorting and merge sorting, especially when dealing with small datasets.
6. Application scenarios of heap sorting
(1) Priority queue implementation:The heap can be used to implement priority queues, especially in scenarios where the maximum or minimum values are frequently obtained (e.g., Dijkstra algorithm, Huffman encoding).
(2) External sorting:When the amount of data is too large and cannot be loaded into memory, heap sorting can effectively sort massive data stored externally.
Summarize
Heap sorting is a sorting algorithm based on heap data structures, with the time complexity of O(n log n) and the spatial complexity of O(1). Although heap sorting is an unstable sorting algorithm, its efficiency and in-situ sorting properties make it very useful in certain scenarios, especially in applications that require frequent access to maximum or minimum values.
The above is a detailed explanation of the steps to implement heap sorting in Java. For more information about Java heap sorting, please pay attention to my other related articles!