LeetCode(347) 数组中的第 K 个最大元素(堆排序)

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

一般情况下,题目中有出现前N个最大(小)值topN、第k个最大(小)值,均可以用堆排序来解答,本文来学习下堆排序的相关知识。

基本概念

堆排序Heapsort)是指利用所设计的一种排序算法。是一个近似完全二叉树的结构,并同时满足的性质:子节点的键值或索引总是小于(或者大于)它的父节点
大根堆:每个节点的值都大于或等于其左右孩子节点的值。
小根堆:每个节点的值都小于或等于其左右孩子节点的值。
完全二叉树:对于深度为k的,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中编号从1n的节点一一对应。
满二叉树:二叉树每一层的节点数都达到最大值。也就是说除最后一层无任何子节点外,每一层上的所有节点都有两个子节点的二叉树。,如果满二叉树的层数为k,第i层的节点数为2^(i - 1),二叉树总结点数为2^k - 1

具体实现

  1. 最大(小)堆调整:将堆的末端子节点作调整,使得子节点永远小于(大于)父节点;
  2. 创建最大(小)堆:将堆中的所有数据重新排序;
  3. 堆排序:移除位在第一个数据的根节点,并做最大(小)堆调整的递归运算;

定义heap[]为存储的数组,长度为n,有以下特点:

  1. 最后一个非叶子节点的位置为n / 2 - 1
  2. 设当前非叶子节点的位置为i,则左叶子节点位置 = 2 * i + 1,右边子节点位置 = 2 * i + 2

大根堆实现

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) {
// 大根堆
BiPredicate<Integer, Integer> predicate = (a, b) -> a > b;
// 小根堆
// BiPredicate<Integer, 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, BiPredicate<Integer, 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, BiPredicate<Integer, 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) {};
}

参考资料

[1]

215. 数组中的第K个最大元素: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/submissions/


原文始发于微信公众号(xiaogan的技术博客):LeetCode(347) 数组中的第 K 个最大元素(堆排序)