本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
一般情况下，题目中有出现前
N个最大（小）值
topN、第
k个最大（小）值，均可以用堆排序来解答，本文来学习下
堆排序的相关知识。
基本概念
堆排序（
Heapsort）是指利用
堆所设计的一种排序算法。
堆是一个近似
完全二叉树的结构，并同时满足
堆的性质：
子节点的键值或索引总是小于（或者大于）它的父节点。
大根堆：每个节点的值都大于或等于其左右孩子节点的值。
小根堆：每个节点的值都小于或等于其左右孩子节点的值。
完全二叉树：对于深度为
k的，有
n个节点的二叉树，当且仅当其每一个节点都与深度为
k的满二叉树中编号从
1至
n的节点一一对应。
满二叉树：二叉树每一层的节点数都达到最大值。也就是说除最后一层无任何子节点外，每一层上的所有节点都有两个子节点的二叉树。，如果满二叉树的层数为
k，第
i层的节点数为
2^(i - 1)，二叉树总结点数为
2^k - 1 。
具体实现
定义
heap[]为存储
堆的数组，长度为
n，有以下特点：
大根堆实现
class Solution {
/**
* 排序后的顺序为从小到大
* @param heap
*/
public void heapSort(int[] heap) {
int length = heap.length;
// 先初始化最大堆
buildMaxHeap(heap, length);
// 调整堆，进入排序逻辑
for(int i = length - 1; i 0; i --) {
// 此时根元素nums[0]为最大值，将其和未排序的最后一个值进行交换
// 这样每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(heap, 0, i);
// 由于堆结构发生了变化，需要继续对根元素nums[0]进行调整
adjustHeap(heap, 0, i);
}
}
/**
* 先初始化最大堆，使其满足所有非叶子节点：父节点的值大于子节点的值；
* @param heap
* @param length 堆长度
*/
public void buildMaxHeap(int[] heap, int length) {
//最后一个非叶子节点的位置为`n / 2 - 1`，从后向前，依次堆化
for(int i = (length 1) - 1; i = 0; i --) {
adjustHeap(heap, i, length);
}
}
/**
* 堆化，使得父节点的值大于子节点的值
* @param heap 堆数组
* @param parent 待调整的非叶子节点
* @param length 调整范围
*/
public void adjustHeap(int[] heap, int parent, int length) {
// index位置节点的左子节点的位置为2 * i + 1
int left = (parent 1) + 1;
// index位置节点的右子节点的位置为2 * i + 2
int right = (parent 1) + 2;
// 存储父节点、左子节点、右子节点三者最大值的位置
int max = parent;
// 比较父节点和左子节点的大小
if(left length && heap[left] heap[max]) {
max = left;
}
// 比较父节点和右子节点的大小
if(right length && heap[right] heap[max]) {
max = right;
}
// 若父节点的值不是三者最大的
if(max != parent) {
// 则交换和最大值子节点的值
swap(heap, parent, max);
// 并继续调整子节点，使其堆化
adjustHeap(heap, max, length);
}
}
/**
* 交换数组heap中i和j的值
* @param heap
* @param i
* @param j
*/
public void swap(int[] heap, int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
小根堆实现
class Solution {
/**
* 排序后的顺序为从大到小
* @param heap
*/
public void heapSort(int[] heap) {
int length = heap.length;
// 先初始化最小堆
buildMinHeap(heap, length);
// 调整堆，进入排序逻辑
for(int i = length - 1; i 0; i --) {
// 此时根元素nums[0]为最小值，将其和未排序的最后一个值进行交换
// 这样每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(heap, 0, i);
// 由于堆结构发生了变化，需要继续对根元素nums[0]进行调整
adjustHeap(heap, 0, i);
}
}
/**
* 先初始化最小堆，使其满足所有非叶子节点：父节点的值小于子节点的值；
* @param heap
* @param length 堆长度
*/
public void buildMinHeap(int[] heap, int length) {
//最后一个非叶子节点的位置为`n / 2 - 1`，从后向前，依次堆化
for(int i = (length 1) - 1; i = 0; i --) {
adjustHeap(heap, i, length);
}
}
/**
* 堆化，使得父节点的值小于子节点的值
* @param heap 堆数组
* @param parent 待调整的非叶子节点
* @param length 调整范围
*/
public void adjustHeap(int[] heap, int parent, int length) {
// index位置节点的左子节点的位置为2 * i + 1
int left = (parent 1) + 1;
// index位置节点的右子节点的位置为2 * i + 2
int right = (parent 1) + 2;
// 存储父节点、左子节点、右子节点三者最小值的位置
int min = parent;
// 比较父节点和左子节点的大小
if(left length && heap[left] heap[min]) {
min = left;
}
// 比较父节点和右子节点的大小
if(right length && heap[right] heap[min]) {
min = right;
}
// 若父节点的值不是三者最小的
if(min != parent) {
// 则交换和最小值子节点的值
swap(heap, parent, min);
// 并继续调整子节点，使其堆化
adjustHeap(heap, min, length);
}
}
/**
* 交换数组heap中i和j的值
* @param heap
* @param i
* @param j
*/
public void swap(int[] heap, int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
通用实现
可以看到大（小）根堆实现的不同逻辑主要在
adjustHeap方法中的判断父节点和子节点的大小，故可以将两者的实现整合到一起；
class Solution {
/**
* 大（小）根堆排序后的顺序为从小（大）到大（小）
*
* @param heap
*/
public void heapSort(int[] heap) {
// 大根堆
BiPredicateInteger, Integer predicate = (a, b) - a b;
// 小根堆
// BiPredicateInteger, Integer predicate = (a, b) - a b;
int length = heap.length;
// 先初始化最大堆
buildHeap(heap, length, predicate);
// 调整堆，进入排序逻辑
for(int i = length - 1; i 0; i --) {
// 此时根元素nums[0]为最大（小）值，将其和未排序的最后一个值进行交换
// 这样每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(heap, 0, i);
// 由于堆结构发生了变化，需要继续对根元素nums[0]进行调整
adjustHeap(heap, 0, i, predicate);
}
}
/**
* 先初始化大（小）根堆，使其满足所有非叶子节点：父节点的值大于（小于）子节点的值；
* @param heap
* @param length 堆长度
*/
public void buildHeap(int[] heap, int length, BiPredicateInteger, Integer predicate) {
//最后一个非叶子节点的位置为`n / 2 - 1`，从后向前，依次堆化
for(int i = (length 1) - 1; i = 0; i --) {
adjustHeap(heap, i, length, predicate);
}
}
/**
* 堆化，使得父节点的值大于（小于）子节点的值
* @param heap 堆数组
* @param parent 待调整的非叶子节点
* @param length 调整范围
*/
public void adjustHeap(int[] heap, int parent, int length, BiPredicateInteger, Integer predicate) {
// index位置节点的左子节点的位置为2 * i + 1
int left = (parent 1) + 1;
// index位置节点的右子节点的位置为2 * i + 2
int right = (parent 1) + 2;
// 存储父节点、左子节点、右子节点三者最大值（最小值）的位置
int temp = parent;
// 比较父节点和左子节点的大小，
// 大根堆的条件为heap[left] heap[temp]
// 小根堆的条件为heap[left] heap[temp]
if(left length && predicate.test(heap[left], heap[temp])) {
temp = left;
}
// 比较父节点和右子节点的大小
// 大根堆的条件为heap[right] heap[temp]
// 小根堆的条件为heap[right] heap[temp]
if(right length && predicate.test(heap[right], heap[temp])) {
temp = right;
}
// 若父节点的值不是三者最大(小)的
if(temp != parent) {
// 则交换和最大（小）值子节点的值
swap(heap, parent, temp);
// 并继续调整子节点，使其堆化
adjustHeap(heap, temp, length, predicate);
}
}
/**
* 交换数组heap中i和j的值
* @param heap
* @param i
* @param j
*/
public void swap(int[] heap, int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
LeetCode 题解
大部分 LeetCode 的堆排序问题，都可以用以上通用实现解决掉，只不过执行用时稍微长点，因为涉及了
Integer的自动装箱（
Autoboxing）与自动拆箱（
Unboxing）。用大（小）根堆的具体实现解决。
215. 数组中的第 K 个最大元素
本题来自 leetCode：215. 数组中的第 K 个最大元素[1]
题目详情
在未排序的数组中找到第
k个最大的元素。请注意，你需要找的是数组排序后的第
k个最大的元素，而不是第
k个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明: 你可以假设
k总是有效的，且
1 ≤ k ≤ 数组的长度。
题目分析
题目要求找到第
k个最大的元素，即大根堆排序时，排序到第
k个元素时，就为所求值；
题目实现
class Solution {
public int findKthLargest(int[] nums, int k) {
heapSort(nums, k);
return nums[nums.length - k];
}
public void heapSort(int[] heap, int k) {
int length = heap.length;
buildMaxHeap(heap, length);
for(int i = length - 1; i = length - k; i --) {
swap(heap, 0, i);
adjustHeap(heap, 0, i);
}
}
// 省略
public void buildMaxHeap(int[] heap, int length) {}
// 省略
public void adjustHeap(int[] heap, int parent, int length) {};
// 省略
public void swap(int[] heap, int i, int j) {};
}
参考资料
原文始发于微信公众号（xiaogan的技术博客）：
