堆排序Java程序
本教程说明如何使用Java编写堆排序程序，这是一种就地排序算法。堆排序使用堆数据结构对元素进行排序，因此显而易见的问题是什么是堆？
堆数据结构
堆是二叉树，因此每个节点最多可以有两个子节点，并且具有以下属性：
这是一棵完整的二叉树，这意味着从左到右读取它完全被填充(所有节点都有2个子节点)，最后一行不需要填充。
在最大堆的情况下，堆中的每个节点都满足每个节点大于或者等于其子节点的条件。如果是最小堆，则节点小于或者等于其子节点。
堆排序算法
编写堆排序Java程序的步骤如下：
从输入数组创建最大堆。使用最大堆排序将以升序进行。对于降序，可以使用最小堆。堆数据结构也使用数组表示。从输入数组创建堆的过程称为heapify。
创建堆后，其根节点就是最大元素。将根元素与数组的最后一个元素交换。
这种交换会干扰堆，因此必须使用数组再次对结构进行堆化。这次最后一个元素已被排除(数组长度减少了一个)，因为它已经在其最终位置。
重复和3，直到排序完成。
如何从数组创建堆
从数组创建堆是堆排序的重要组成部分，因此理解它很重要。
数组被视为完整的二叉树，每个元素都被视为一个节点。在每个节点的数组中，我们可以使用以下公式获取其父节点，左子节点和右子节点：
对于数组中索引为i的节点，
父节点为–(i-1)/ 2
左子节点为-2 * i +1
右子节点为-2 * i + 2
要创建堆，我们必须从底部的节点开始，然后向上移动以比较子节点是否大于父节点，如果是，则交换节点值。由于最后一级具有叶节点(没有子级的节点)，因此此比较必须从上一级开始。
对于长度为n的数组，最后一个节点将在索引(n-1)处，因此使用等式，其父节点的索引应为(n-1)/ 2. 堆数组从该父节点开始，在每次迭代中将父节点与左子节点和右子节点进行比较，如果子节点大于父节点，则交换节点。
例如，如果输入数组为[5、12、3、16、8、10]，则该数组的完整二叉树可以直观地表示为
由于最后一个索引为5，因此父节点应位于索引(5-1)/ 2 =2. 创建堆的过程从该索引2开始。将索引2处的节点与其子节点进行比较，如果有任何子节点，则进行交换大于父节点。在我们的树10> 3中，将交换这些值。当索引为1时，将索引1处的节点与其子节点进行比较，并在需要时交换值。
在下一次迭代中，对索引0进行比较和交换。
堆排序Java程序
public class HeapSort {
public static void main(String[] args) {
int[] arr = {5, 12, 3, 16, 8, 10};
System.out.println("Original array- " + Arrays.toString(arr));
HeapSort hs = new HeapSort();
hs.heapSort(arr);
System.out.println("Sorted array after heap sort- " + Arrays.toString(arr));
}
private void heapSort(int[] arr){
int arrLength = arr.length;
// create heap from array start from index (n-1)/2
for(int i = (arrLength-1)/2; i >= 0; i--){
heapify(arr, arrLength, i);
}
System.out.println("heapified array- " + Arrays.toString(arr));
// Heap Sort
for(int i = arrLength-1; i >= 0; i--){
// Swap root and last nodes
swap(arr, i, 0);
// Reconstruct heap again
heapify(arr, i, 0);
}
}
private void heapify(int[] numArr, int index, int i){
// Getting parent and children indexes
int root = i;
int leftChild = 2*i + 1;
int righChild = 2*i + 2;
//compare left child value
if(leftChild < index && numArr[leftChild] > numArr[root])
root = leftChild;
//comparing right child value
if(righChild < index && numArr[righChild] > numArr[root])
root = righChild;
// swap values if required and call method recursively for next level
if(root != i){
swap(numArr, root, i);
heapify(numArr, index, root);
}
}
private void swap(int[] numArr, int index, int li){
int temp = numArr[li];
numArr[li] = numArr[index];
numArr[index] = temp;
}
}
堆排序时间和空间的复杂性
执行任何常见树操作所需的时间为O(logn)。对于堆排序，堆创建是针对n个元素完成的，因此堆排序的时间复杂度为O(n * logn)。时间复杂度保持不变，但是数据是分布式的。那是堆排序比快速排序得分更高的地方，快速排序是另一种O(n * logn)排序算法。在最坏的情况下，快速排序可能会变为O(n2)，但堆排序始终为O(n * logn)。
由于相同的数组用于按顺序排列元素，因此不存在额外的空间需求。因此，堆排序的空间复杂度为O(1)。
