题解 |NO.46 #最小的K个数#3.14

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param input int整型一维数组
 * @param inputLen int input数组长度
 * @param k int整型
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */

//向下调整
void down(int heap[], int sit, int heapLen) {
    int i = 2 * sit;
    int temp = 0;
    while (i < heapLen) {
        if (i + 1 < heapLen && heap[i + 1] > heap[i])
            i = i + 1;
        if (heap[sit] < heap[i]) {
            temp = heap[sit];
            heap[sit] = heap[i];
            heap[i] = temp;
            sit = i;
            i = 2 * sit;
        }
        else {
            return;
        }
    }
}

/*/向上调整			这部分没有用到
void up(int heap[], int sit){
    int i = sit / 2;
    int temp = 0;
    while(i >= 0){
        if(heap[sit] > heap[i]){
            temp = heap[sit];
            heap[sit] = heap[i];
            heap[i] = temp;
            sit = i;
            i = sit / 2;
        }
        else {
            return;
        }
    }
}*/

//建大顶堆
void creatMaxHeap(int heap[], int heapLen) {
    int i = heapLen / 2;
    for(; i >= 0; i--){
        down(heap, i, heapLen);
    }
    return;
}

int* GetLeastNumbers_Solution(int* input, int inputLen, int k,
                              int* returnSize ) {
    if(k == 0 || inputLen == 0)
        return NULL;
    /*/建立heap数组用来存储最小的k个元素		不需要再另外建立一个heap数组，直接用input即可
    int heap[k];
    for (int i = 0; i < k; i++)
        heap[i] = input[i];*/
    //将input前k项调整为大顶堆
    creatMaxHeap(input, k);
    //依次比较剩余元素与堆顶元素大小
    for(int i = k; i < inputLen; i++){
        if(input[i] < input[0]){
            input[0] = input[i];
            down(input, 0, k);
        }
    }
    *returnSize = k;
    return input;		//如果另外定义heap数组，返回时会出现错误，不能返回局部变量的地址
}