最大（小）堆-数组中第K大元素

数组中第K大元素.png
最大（小）堆
1. 基本函数接口
（1）新增item
i. 新增item 放到arr[size]
ii. float arr[size]
iii size++
（2）popMax 最大值
i. 取出最值
ii. 将最后一个item 放到arr[0]
iii. sink
2. 支撑接口：
（1）float：用于新增item (arr[size])时，保持堆头的最值语义
（2）sink：用于pop最值arr[0]时，保持堆头的最值语义
（3）swap：用于float 和 sink 的值交换

struct Heap{
    int *arr;
    int size;
    int capacity;
};
#define MAX_HEAP_SIZE (100001)
#define PARENT(i) ((i-1)/2)
#define LEFT(i) (i*2+1)
#define RIGHT(i) (i*2+2)
struct Heap* init(void)
{
    struct Heap *heap = (struct Heap *)malloc(sizeof(struct Heap));
    heap->size = 0;
    heap->capacity = MAX_HEAP_SIZE;
    heap->arr = (int *)malloc(sizeof(int)*MAX_HEAP_SIZE);
    return heap;
}

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

void __float(struct Heap *obj, int index)
{
    int *arr = obj->arr;
    while(index && arr[index] > arr[PARENT(index)] ) {
        swap(&arr[index], &arr[PARENT(index)]);
        index = PARENT(index);
    }
}

void insert(struct Heap *obj, int value)
{
    obj->arr[obj->size]=value;
    __float(obj, obj->size);
    obj->size++;
}

void sink(struct Heap *obj, int index)
{
    int *arr = obj->arr;
    int size = obj->size;
    int left = LEFT(index);
    int right = RIGHT(index);
    int maxIndex = index;

    if(left < size && arr[left] > arr[maxIndex]) {
        maxIndex = left;
    }

    if(right < size && arr[right] > arr[maxIndex]) {
        maxIndex = right;
    }

    if (maxIndex != index) {
        swap(&arr[index], &arr[maxIndex]);
        sink(obj, maxIndex);
    }
}

int popMax(struct Heap *obj) {
    int max = obj->arr[0];
    obj->arr[0] = obj->arr[obj->size-1];
    obj->size--;
    sink(obj, 0);
    return max;
}
int findKthLargest(int* nums, int numsSize, int k){
    struct Heap* obj = init();
    int i;
    int kLargest;
    for(i=0;i<numsSize;i++) {
        insert(obj, nums[i]);
    }
    for(i=0;i<numsSize;i++) {
        std::cout<< i << ": "<<obj->arr[i]<<std::endl;
    }
    while(k) {
        kLargest = popMax(obj);
        std::cout<< k << ": "<< kLargest<<std::endl;

        k--;
    }

    return kLargest;
}