Java 中的堆排序

Java中的堆排序是一种基于比较的排序技术，其中使用了数据结构二叉堆。这种排序与选择排序几乎相同，选择最大的元素放在最后，然后对所有元素重复该过程。为了理解堆排序，让我们看看Java中的二叉堆排序。

• 基于树的数据结构。
• 完全二叉树。
• 它最多可以有两个孩子。
• 根节点中的值可以更大（最大堆）或更小（最小堆）

Java 中堆排序是如何工作的？

在讨论算法之前，让我们先看看 Heapify 是什么。

广告 该类别中的热门课程 JAVA 掌握 - 专业化 | 78 课程系列 | 15 次模拟测试

Heapify

使用输入数据创建堆后，堆属性可能不满足。为了实现这一点，将使用一个名为 heapify 的函数来调整堆节点。如果我们想创建一个最大堆，当前元素将与其子元素进行比较，如果子元素的值大于当前元素，则将与左或右子元素中最大的元素进行交换。类似地，如果需要创建最小堆，则将使用左子或右子元素中的最小元素进行交换。例如，以下是我们的输入数组，

我们可以将其视为一棵树而不是一个数组。第一个元素将是根；第二个将是根的左子节点；第三个元素将是根的右子元素，依此类推。

为了将堆转换为树，请以自下而上的方向遍历树。由于叶节点没有子节点，所以让我们看看下一个级别。即 5 和 7。

我们可以从左边的 5 点开始。这里，5有两个子节点：9和4，其中9大于父节点5。为了使父节点更大，我们将交换5和9。交换后，树将如下所示。

让我们转到下一个元素 7，其中 8 和 2 是子元素。与元素 9 和 4 类似，7 和 8 将被交换，如下图所示。

最后，3 有两个子节点 - 9 和 8，其中 9 在子节点和根节点中较大。因此，将交换 3 和 9 以使根更大。重复该过程，直到形成有效的堆，如下所示。

堆升序排序算法

1. 使用输入数据创建最大堆
2. 用堆中最大的元素替换最后一个元素
3. 堆满树
4. 重复该过程，直到数组排序完毕

堆降序排序算法

1. 使用输入数据创建最小堆
2. 用堆中最小的元素替换最后一个元素
3. 堆满树
4. 重复该过程，直到数组排序完毕

现在，让我们尝试使用给定的算法对上面获得的堆进行升序排序。首先，删除最大的元素。即 root 并将其替换为最后一个元素。

现在，堆化形成的树并将删除的元素插入到数组的最后一个，如下所示。

再次删除根元素，将其替换为最后一个元素并对其进行堆化。

将移除的元素插入到空出的位置。现在您可以看到数组的末尾正在排序。

现在，删除元素 7 并将其替换为 2。

堆积树，如下所示。

重复这个过程，直到数组排序完毕。删除元素 5。

堆积树。

删除元素 4。

再次欢腾。 

最后就会形成这样一个排序数组。

示例

现在让我们看看Java中堆排序的源码

//Java program to sort the elements using Heap sort
import java.util.Arrays;
public class HeapSort {
public void sort(int array[]) {
int size = array.length; //Assigning the length of array in a variable
// Create heap
for (int i = size / 2 - 1; i >= 0; i--)
heapify(array, size, i);
//Find the maximum element and replace it with the last element in the array
for (int i=size-1; i>=0; i--) {
int x = array[0];//largest element(It is available in the root)
array[0] = array[i];
array[i] = x;
// Recursively call <u>heapify</u> until a heap is formed
heapify(array, i, 0);
}
}
// <u>Heapify</u> function
void heapify(int array[], int SizeofHeap, int i) {
int largestelement = i; // Set largest element as root
int leftChild  = 2*i + 1; // index of left child = 2*i + 1
int rightChild  = 2*i + 2; //index of right child  = 2*i + 2
// left child is greater than root
if (leftChild  < SizeofHeap && array[leftChild ] > array[largestelement])
largestelement = leftChild ;
//right child is greater than largest
if (rightChild  < SizeofHeap && array[rightChild ] > array[largestelement])
largestelement = rightChild ;
// If <u>largestelement</u> is not root
if (largestelement != i) {
int temp = array[i];
array[i] = array[largestelement];
array[largestelement] = temp;
// Recursive call to  heapify the sub-tree
heapify(array, SizeofHeap, largestelement);
}
}
public static void main(String args[]) {
int array[] = {3,5,7,9,4,8,2};
System.<em>out</em>.println("Input array is: " + Arrays.<em>toString</em>(array));
HeapSort obj = new HeapSort();
obj.sort(array);
System.<em>out</em>.println("Sorted array is : " + Arrays.<em>toString</em>(array));
}
}

输出

结论

堆排序是一种依赖于二叉堆数据结构的排序技术。它几乎类似于选择排序，并且不使用单独的数组进行排序和堆。

 推荐文章

这是 Java 堆排序的指南。在这里，我们讨论工作的升序和降序排序算法以及带有示例代码的示例。您还可以阅读我们其他推荐的文章以了解更多信息 –

1. Java 中的合并排序
2. C 中的堆排序
3. C++ 中的堆排序
4. 数据结构中的选择排序

以上是Java 中的堆排序的详细内容。更多信息请关注PHP中文网其他相关文章！