这次在刷Leetcode时，在求解数组中的第K大问题时，想到了使用堆排序，因此本篇文章用于巩固对堆排序的学习以及代码实现。
题目描述：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
输入：[3,2,3,1,2,4,5,5,6] 和 k = 4
输出：4
当时看到此题时，第一反应就是想到使用大顶堆来求解，在第K次调堆后，就能够得到最K大元素。后续以大顶堆进行为例。
先来简单回顾堆排序：堆是一棵完全二叉树。如果是一个大顶堆，则根节点递归的大于其左右孩子节点的值。
以大顶堆为例：(3,2,3,1,2,4,5,5,6)，对该待排序列进行堆排序。
首先，将该序列建立一棵完全二叉树。(这里可以假定建立完全二叉树，可以以数组的位序模拟对二叉树的操作)。
从第一个(从右向左，从下向上看起)非叶子节点为根节点的子树开始，将其调整为大根堆。因为6>5，所以6和1进行交换。
开始调整第二个非叶子节点作为根节点的子树，这里第二个非叶子节点为3。因为5>4，所以根节点3和5进行交换。
接下来，来到非叶节点2，因为 6 > 2，所以根节点2与6进行交换。此时，该子树因为根的调整，以2为根节点的子树不满足大顶堆的性质，因此需要递归的调整子树，将5和2进行调换。
此时来到最后一个非叶节点，即根节点。因为6 > 5，所以3和6进行调换，同时需要递归修改此时以3为根节点的子树进行调整为大顶堆。
至此，最后得到的一个二叉树就为大顶堆，每个节点的值都大于其左右子树的值。其中，根节点为最大值，就是第一大元素。
将根节点输出，以最后一个叶子节点将其补上，然后重复上述的步骤。
备注：当左、右节点值相同时，替换哪一个依据代码的具体形式。
该题解的具体代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| class Solution {
public int findKthLargest(int[] nums, int k) {
return maxHeapMethod(nums,k);
}
public int maxHeapMethod(int[] nums,int k) {
int heapLength = nums.length;
generateHeap(nums);
for(int i = nums.length - 1;i > nums.length - k;--i){
swapNums(nums,0,i);
heapLength -= 1;
adjustHeap(nums,0,heapLength);
}
return nums[0];
}
private void generateHeap(int[] splitNums){
int heapLength = splitNums.length;
for(int i = heapLength / 2;i >= 0;--i) {
adjustHeap(splitNums,i,heapLength);
}
}
private void adjustHeap(int[] splitNums,int rootIndex,int heapLength) {
int leftIndex = rootIndex * 2 + 1;
int rightIndex = rootIndex * 2 + 2;
int maxIndex = rootIndex;
if(leftIndex < heapLength && splitNums[leftIndex] > splitNums[maxIndex]) {
maxIndex = leftIndex;
}
if(rightIndex < heapLength && splitNums[rightIndex] > splitNums[maxIndex]) {
maxIndex = rightIndex;
}
if(maxIndex != rootIndex) {
swapNums(splitNums,rootIndex,maxIndex);
adjustHeap(splitNums,maxIndex,heapLength);
}
}
private void swapNums(int[] nums,int indexA,int indexB) {
int temp = nums[indexA];
nums[indexA] = nums[indexB];
nums[indexB] = temp;
}
}
|
