Find k-th max

kthmax.c

#include <assert.h>
#include <stdio.h>
// Method 1 start
void exch(int *a, int i, int j) {
  int t = a[i];
  a[i] = a[j];
  a[j] = t;
}

int partition(int *a, int lo, int hi) {
  int povit = a[lo];
  int i = lo;
  for (int j = lo + 1; j <= hi; j++) {
    if (a[j] >= povit) {
      i++;
      exch(a, i, j);
    }
  }
  exch(a, i, lo);
  return i;
}

int k_th_max1(int *a, int size, int k) {
  if (!a || k > size || k <= 0) return -1;
  int lo = 0, hi = size - 1;
  int p = partition(a, lo, hi);
  while (p != k - 1) {
    if (k - 1 < p) {
      hi = p - 1;
      p = partition(a, lo, hi);
    } else {
      lo = p + 1;
      p = partition(a, lo, hi);
    }
  }
  return a[k - 1];
}
// Method 1 end

// Method 2 start

void sink(int *heap, int i, int size) {
  while (2 * i <= size) {
    int j = 2 * i;  // select min child
    if (j < size && heap[j] > heap[j + 1]) j++;
    if (heap[i] <= heap[j]) break;  // not need to adjust
    exch(heap, i, j);
    i = j;
  }
}

void build_min_heap(int *heap, int size) {
  for (int i = size / 2; i >= 1; i--) {
    sink(heap, i, size);
  }
}

int k_th_max2(int *a, int size, int k) {
  int heap[k + 1];
  for (int i = 0; i < k; i++) {
    heap[i + 1] = a[i];
  }
  build_min_heap(heap, k);
  for (int i = k; i < size; i++) {
    if (a[i] > heap[1]) {
      heap[1] = a[i];
      sink(heap, 1, k);
    }
  }
  return heap[1];
}
// Method 2 end

int main(int argc, char const *argv[]) {
  int a[] = {3, 1, 6, 2, 10, 8, 4, 9, 5, 0, 7};
  for (int i = 1; i <= 11; i++) {
    int max1 = k_th_max1(a, 11, i);
    int max2 = k_th_max2(a, 11, i);
    assert(max1 == max2);
    printf("%2d-th max: %d\n", i, max1);
  }
  return 0;
}