编辑代码

#include <stdio.h>

void swap(int *a, int *b){
    int c = *a;
    *a = *b;
    *b = c;
}

void heap_adjust(int *arr, int len, int index) {	//构造大顶堆
    if(index<0 || index>len || 2*index+1 >= len) 	return;	
    						//保证有子节点的根节点进行构造
    
    int max = 2*index+1;	//当前节点左子节点序号
    
    if(max+1 < len && arr[max+1] > arr[max])	max++;	//向后比较，找出最大值
    
    if(arr[max] > arr[index]){		//子节点比根节点大，交换
        swap(&arr[max], &arr[index]);
        heap_adjust(arr, len, max);		//当前最大值节点为根，递归
    }
}

int findKthLargest(int* arr, int len, int k){
    int i;
    
    for(i=len/2; i>=0; i--)	 heap_adjust(arr, len, i);	//自底向上构造大顶堆
    
    for(i=0; i<k; i++){		//每次将最大值放最后，进行k次
        heap_adjust(arr, len-i, 0);		
        swap(&arr[0], &arr[len-i-1]);
    }
    
    return arr[len-k];	//倒数第k个数
}

int main () {
       int arr[]={6,5,2,8,10,9};
       int k =  findKthLargest(arr,6,1);
       printf("%d ",k);
}