堆结构就是用数组实现的完全二叉树结构，也叫做优先级队列结构,堆排序是利用堆这种数据结构而设计的一种排序算法， 堆排序是一种选择排序， 它的最坏， 最好平均时间复杂度均为 O(nlogn)， 它也是不稳定排序。
堆是具有以下性质的完全二叉树： 每个结点的值都大于或等于其左右孩子结点的值， 称为大顶堆（注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系,）每个结点的值都小于或等于其左右孩子结点的值， 称为小顶堆
对于任意一颗完全二叉树，它的任意的父子节点都有以下规律：
1. 父节点的下标(Findex)对应的两个左右节点，左节点下标为2Findex+1，右节点下标为2Findex+2
2. 对于任意子节点(Sindex)，他的父节点下标为(Sindex - 1)/2
根据以上介绍，我们现在来实现堆排序：
1.首先我们来看构建大顶堆的两个主要方法:
heapInsert: 向堆中加入元素,先加在末尾，然后通过比较其与父节点之间的大小关系不断向上交换。直到子节点的值小于父节点。
heapify: 将以index位置为根节点的树调整为大根堆的形式
注意: 以上方法也可以构建小根堆，只是条件稍微改变一下
2.通过heapInsert首先将数组构成一个大根堆O(N * logN)(如果数组已经给出，则也可以使用heapify方法进行构建，时间复杂度更低 O(N))
3.整个序列的最大值就是堆顶的根节点。
4.将其与末尾元素进行交换， 此时末尾就为最大值
5.然后将剩余 n-1 个元素通过heapify重新构造成一个堆， 这样会得到 n 个元素的次小值。 如此反复执行， 便能得到一个有序序列了
因为堆排序使用到了大根堆，所以先来实现大根堆：
// 大根堆
public class MaxHeap {
private int[] heap;
private final int limit;
private int heapSize;
public MaxHeap(int limit) {
this.heap = new int[limit];
this.limit = limit;
this.heapSize = 0;
}
public boolean isEmpty() {
return heapSize == 0;
}
public boolean isFull() {
return heapSize >= limit;
}
public void push(int value) {
if (heapSize == limit) {
throw new RuntimeException("heap is full");
}
heap[heapSize] = value;
heapInsert(heap, heapSize++);
}
public int pop() {
int res = heap[0];
swap(heap, 0, --heapSize);
heapify(heap, 0, heapSize);
return res;
}
// 新加进来的数，现在停在了index位置，请依次往上移动，
// 移动到0位置，或者干不掉自己的父亲了，停！
private void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
// 从index位置，往下看，不断的下沉
// 停：较大的孩子都不再比index位置的数大；已经没孩子了
private void heapify(int[] arr, int index, int heapSize) {
int left = 2 * index + 1;
while (left < heapSize) { // 如果有左孩子，判断有没有右孩子，可能有可能没有！
// 如果有右孩子，比较左右孩子哪个更大，没有就返回左孩子下标
int largest = (left + 1) < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
// 再比较左右孩子中较大的节点值和index值谁大谁小，返回更大的值的节点下标
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) { // 自己就是最大的
break;
}
swap(arr, largest, index);
index = largest;
left = 2 * index + 1;
}
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
堆排序
public class HeapSort {
public static void main(String[] args) {
int[] arr = {2,3,5,1,2,7,4,1};
HeapSort heapSort = new HeapSort();
heapSort.heapSort(arr);
for (int i : arr) {
System.out.print(i + " "); // 1 1 2 2 3 4 5 7
}
}
public void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int heapSize = arr.length;
// 先将数组元素存放到大顶堆中
for (int i = 0; i < arr.length; i++) {
heapify(arr, 0, heapSize);
}
// 因为是大顶堆，每一次将数组头元素(最大值)放到数组的最后，heapSize减一
// 这样数组的后面存放的就是每次取到的最大值，然后将这个最大值移出堆的管理范围
// 依次类推最终就得到了排好序的数组
swap(arr, 0 , --heapSize);
while (heapSize > 0) {
heapify(arr, 0 , heapSize);
swap(arr, 0 , --heapSize);
}
}
// 新加进来的数，现在停在了index位置，请依次往上移动，
// 移动到0位置，或者干不掉自己的父亲了，停！
private void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
// 从index位置，往下看，不断的下沉
// 停：较大的孩子都不再比index位置的数大；已经没孩子了
private void heapify(int[] arr, int index, int heapSize) {
int left = 2 * index + 1;
while (left < heapSize) { // 如果有左孩子，判断有没有右孩子，可能有可能没有！
// 如果有右孩子，比较左右孩子哪个更大，没有就返回左孩子下标
int largest = (left + 1) < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
// 再比较左右孩子中较大的节点值和index值谁大谁小，返回更大的值的节点下标
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) { // 自己就是最大的
break;
}
swap(arr, largest, index);
index = largest;
left = 2 * index + 1;
}
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
相关习题(小根堆)
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。
选择一个合适的排序策略，对这个数组进行排序
每次将K个数加入到一个小根堆中，然后每次取出最小值放到数组从头开始的位置依次向后。
最终将后K个元素从小根堆中取出放入元素值即可。
import java.util.PriorityQueue;
public class SortArrayDistanceLessK {
public static void sortedArrDistanceLessK(int[] arr, int k) {
PriorityQueue heap = new PriorityQueue<>();
int index = 0;
for (; index <= Math.max(arr.length - 1, k - 1); index++) {
heap.add(arr[index]);
}
int i = 0;
// i ~ index 就是小根堆范围
// 取范围中最小值(小根堆 堆顶元素)，放到i位置，然后递进
for (; index < arr.length - 1; index++, i++) {
heap.add(arr[index]);
arr[i] = heap.poll();
}
// 最终将其余元素根据小根堆顺序，依次放入arr后几个位置即可
while (!heap.isEmpty()) {
arr[i++] = heap.poll();
}
}
public static void main(String[] args) {
int[] arr = {2, 1, 4, 5, 3};
int k = 2;
sortedArrDistanceLessK(arr, k);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
