java 数据结构之堆排序（HeapSort）详解及实例

最大堆的任意子树根节点不小于任意子结点，最小堆的根节点不大于任意子结点。所谓堆排序就是利用堆这种数据结构的性质来对数组进行排序，在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的性质可知，最大的值一定在堆顶。堆排序一种不稳定的排序算法，其时间复杂度为O。构建最大堆； 堆排序中最重要的算法就是maxHeap，该函数假设一个元素的两个子节点都满足最大堆的性质，只有根元素可能违反最大堆性质，那么把该元素以及左右子节点的最大元素找出来，如果该元素已经最大，那么整棵树都是最大堆，程序退出，否则交换根元素与最大元素的位置，继续调用maxHeap构建最大元素所在的子树。