3. Java code implementation and time complexity analysis
One, the introduction
Priority queues can be used to sort in O(NlogN) time, just as the idea used in solving the topK problem in the previous article is called heapsort.
2. Graphic Heapsort
- Algorithm idea: heap ordering (build the big top heap) by buildHeap array elements; N-1 more deleteMax to the heap. Here’s the trick, if you’re using a new array, you need O(N) space; But each time deleteMax will empty a space and filter down the nodes at the end, we can put deleteMax’s data at the end.
- Heap sort process:
If you don’t know about binary heap, you can look at the diagram priority queue.
Java code implementation and time complexity analysis
We start at index 0, unlike the binary heap that starts at index 1.
- Code implementation
public class Heapsort {
public static void main(String[] args) {
Integer[] integers = {7.1.13.9.11.5.8};
System.out.println("Original sequence:" + Arrays.toString(integers));
heapsort(integers);
System.out.println("After sorting:" + Arrays.toString(integers));
}
public static <T extends Comparable<? super T>> void heapsort(T[] a) {
if (null == a || a.length == 0) {
throw new RuntimeException("Array null or length 0");
}
/ / build the heap
for (int i = a.length / 2 - 1; i >= 0; i--) {
percDown(a, i, a.length);
}
//deleteMax
for (int i = a.length - 1; i > 0; i--) {
swapReferences(a, 0, i);
percDown(a, 0, i);
}
}
/ * *
* Method of filtering down
*
* @paramA: Array to be sorted
* @paramI: Which index to filter from
* @paramN: logical size of the binary heap
* @param <T>
* /
private static <T extends Comparable<? super T>> void percDown(T[] a, int i, int n) {
int child;
T tmp;
for (tmp = a[i]; leftChild(i) < n; i = child) {
child = leftChild(i);
if(child ! = n -1 && a[child].compareTo(a[child + 1]) < 0) {
child++;
}
if (tmp.compareTo(a[child]) < 0) {
a[i] = a[child];
} else {
break;
}
}
a[i] = tmp;
}
private static int leftChild(int i) {
return 2 * i + 1;
}
/ * *
* Swap elements at two positions in an array
*
* @paramA: Target array
* @paramIndex1: Index of the first element
* @paramIndex2: Index of the second element
* @param <T>
* /
private static <T> void swapReferences(T[] a, int index1, int index2) {
T tmp = a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
}
// Output the result
// Original sequence: [7, 1, 13, 9, 11, 5, 8]
// Sort: [1, 5, 7, 8, 9, 11, 13]
Copy the code-
Time complexity: buildHeap uses O(N) time, the element filters down O(logN), filters down n-1 times, so total O(N+(n-1)logN) = O(NlogN). As can be seen from the procedure, heap sort, regardless of best or worst time complexity is stable at O(NlogN).
-
Space complexity: Using its own storage, no doubt O(1).
Four,
This paper illustrates the process of heap sort by drawing a picture, clearly know heap sort first through heap ordering, and then through deleteMax sort. Its space complexity is O(1) and time complexity is stable at O(NlogN).