title: Java实现堆排序
date: 2019-12-26 18:26:51
tags: 数据结构与算法
categories: 数据结构与算法
背景
过完年就要春招了，数据结构和算法是面试中的重要内容，尤其是数据结构。趁着最近已经基本没课，时间比较多，学习一些比较常见的算法。今天刚学会堆排序，写篇博客记录一下。
描述
什么是堆？
学习堆排序，那我们首先得知道，什么是堆。堆其实就是一棵完全二叉树，分为两种：
大根堆：每个根节点的值都比它左右节点的值要大；小根堆：每个根节点的值都比它左右节点的值要小；
若用数组存储一个完全二叉树，那根节点的索引与左右子节点的索引满足以下条件：
- 左子节点索引 = 根节点索引 × 2 + 1；
- 右子节点索引 = 根节点索引 × 2 + 2；
如何建立堆
以大根堆为例，我们知道，在大根堆中，每一个根节点的值，都大于它左右节点的值，而建堆的过程，其实就是调整这棵完全二叉树中节点的位置。我们从最后一个根节点开始，调整节点的位置，若当前根节点的值小于其子节点的值，则将值最大的子节点与根节点交换，交换过程实际上就是交换数组中的两个位置的值，通过上面说的根节点与子节点索引的关系；此过程结束，继续上一个根节点，重复此过程，直到整个堆的根节点置换完毕，则堆建立完毕。
假设堆中一共有n个节点，那最后一个根节点的下标就是n/2-1，因为在完全二叉树中，共有n/2个子节点。所以我们可以知道，在存储的数组中，0 ~ n/2-1都是非叶子节点，后面的都是叶子节点，所以建堆就是从n/2-1到0这些非叶子结点以此进行。
如何进行堆排序
我们建立好大根堆后，堆顶元素就是所有数中最大的了，此时我们将堆顶与数组中的最后一位置交换，然后再将1 ~ n-1个元素建立成大根堆，并将堆顶与数组中第n-1个位置交换，以此类推，每次都能得到剩余值中最大的值，放到最后。进行n-1次，则就得到了一个有序的数组了。
代码
import java.util.Arrays;
/**
* Java实现堆排序
*/
@SuppressWarnings("all")
public class HeapSort {
public static void main(String[] args) {
int[] a = {4,1,2,5,3,8,6};
heapSort(a);
System.out.println(Arrays.toString(a));
}
/**
* 堆排序
* @param arr
* @return
*/
public static int[] heapSort(int[] arr) {
int len = arr.length;
// 建立初始大根堆
buildMaxHeap(arr, len);
// 依次将堆顶的最大值放到数组的最后，并重新建堆
for (int i = len - 1; i > 0; --i) {
swap(arr, 0, i);
len--;
heapity(arr, 0, len);
}
return arr;
}
/**
* 建立初始大根堆
* @param arr
* @param len
*/
private static void buildMaxHeap(int[] arr, int len) {
// 遍历所有非叶子节点，进行建堆操作
// 在完全二叉树中，共n个节点，则0 ~ (n/2)-1为非叶子节点
for (int i = len / 2 - 1; i >= 0; --i) {
heapity(arr, i, len);
}
}
/**
* 建立大根堆的过程中，调整节点位置
* @param arr 表示完全二叉树的数组
* @param root 当前的根节点
* @param len 数组中，堆的长度
*/
private static void heapity(int[] arr, int root, int len) {
// 计算左右节点的在数组中的位置
int left = (root << 1) + 1;
int right = (root << 1) + 2;
// 初始化当前子树的最大值的位置为根节点的位置
int max = root;
// 判断左节点是否越界，若没有越界，则判断左节点是否大于根节点
// 若大于，则将max记录为左节点的下标
if (left < len && arr[left] > arr[max]) {
max = left;
}
// 判断右节点是否越界，若没有越界，再判断右节点的值是否大于max节点的值
// 若大于，则更新，max的值为右节点下标
if (right < len && arr[right] > arr[max]) {
max = right;
}
// 判断当前的最大值节点是否为根节点，若不是，则将最大值节点与根节点交换
if (root != max) {
swap(arr, root, max);
// 递归交换子树的节点
heapity(arr, max, len);
}
}
/**
* 交换数组中两个位置的值
* @param arr
* @param l
* @param r
*/
private static void swap(int[] arr, int l, int r) {
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
}
参考博客
https://www.cnblogs.com/lanhaicode/p/10546257.html