public class KthLargest {
public static void main(String[] args){
System.out.println(findKthLargest(new int[] {3,2,1,5,6,4} , 2)) ;
}
//heapsort-->find kth
public static 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;
maxiHeapify(nums, 0, heapsize);
}
return nums[0];
}
public static void swap(int[] a, int i, int largest){
int temp=a[i];
a[i]=a[largest];
a[largest]=temp;
}
public static void buildHeap(int a[], int heapsize){
for(int i=heapsize/2-1;i>=0;i--){
maxiHeapify(a,i,heapsize);
}
}
public static void maxiHeapify(int[] a, int i, int heapsize) {
int left=i*2+1;
int right=2*i+2;
int largest=i;
if(left<heapsize&&a[left]>a[largest]){
largest=left;
}
if(right<heapsize&a[right]>a[largest]){
largest=right;
}
if(largest!=i){
swap(a,i,largest);
maxiHeapify(a, largest, heapsize);
}
}
}
Heapsort
建堆
从堆的中间开始,依次向下调整,传参调整第i个结点
public static void buildHeap(int a[], int heapsize){
for(int i=heapsize/2-1;i>=0;i--){
AdjustHeap(a,i,heapsize);
}
}
调整
判断结点 i 的左孩子和右孩子是否比i的值大,如果大就交换并继续调整交换后的堆;反之不变
public static void AdjustHeap(int[] a, int i, int heapsize) {
int left=i*2+1;
int right=2*i+2;
int largest=i;
if(left<heapsize&&a[left]>a[largest]){
largest=left;
}
if(right<heapsize&a[right]>a[largest]){
largest=right;
}
if(largest!=i){
swap(a,i,largest);
AdjustHeap(a, largest, heapsize);
}
}
public static void swap(int[] a, int i, int largest){
int temp=a[i];
a[i]=a[largest];
a[largest]=temp;
}
堆排序
- 建堆
- 利用for loop 从最后一个结点开始,将堆顶元素与堆底元素交换
- 调整,找到最大值的正确位置
public static void findKthLargest(int[] nums,int k){
int heapsize=nums.length;
buildHeap(nums,heapsize);
for(int i=nums.length-1;i>=0;--i) {
swap(nums,0,i);//交换堆顶与堆底元素,找到最大元素的最终正确位置
--heapsize;//最大值已经找到正确位置,不再参与排序
AdjustHeap(nums, 0, heapsize);
}
}
标签:nums,int,堆排序,static,heapsize,largest,public
From: https://www.cnblogs.com/mubai-xx/p/17097191.html