找出乱序数组第k大的数字（堆排序专场）
使用堆排序来解决《乱序数组第k大的数字》先放上代码（虽然leetcode要求O(n)，但是堆排序是O(nlogn)）
`class Solution {
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
buildHeap(nums, heapSize);
for(int i = nums.length - 1; i >= nums.length - k + 1; i--) {
swap(nums, 0, i);
heapSize--;
buildHeap(nums, heapSize);
}
return nums;
}
public void buildHeap(int[] nums, int heapSize) {
for(int i = heapSize / 2 - 1; i >= 0; i--) {
maximum(nums, i, heapSize);
}
}
public void maximum(int[] nums, int root, int heapSize) {
int lChild = root * 2 + 1;
int rChild = root * 2 + 2;
int largest = root;
if (lChild < heapSize && nums > nums) {
largest = lChild;
}
if (rChild < heapSize && nums > nums) {
largest = rChild;
}
// 如果largest不再是入参那个根节点，说明有子节点比它大，要换，换了之后继续往下递归看还有没有
if (largest != root) {
swap(nums, root, largest);
maximum(nums, root, largest);
}
}
public void swap(int[] nums, int a, int b) {
int temp = nums;
nums = nums;
nums = temp;
}}`
比较有收获的几个点：
[*]堆里面儿子节点是父亲节点n的n2+1和n2+2
[*]删除堆的堆顶是通过把堆顶元素和堆最后的元素交换，并且heapSize--来实现的
[*]如果有儿子节点比父亲节点大，那么需要交换父亲节点和这个儿子节点，并且继续将交换之后新的儿子节点作为新的根节点往下递归判断
[*]可以从heapSize/2这个节点开始判断，并不断--，最后得到的数组就是正确的堆顶，进行进一步处理即可
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]