215. Kth largest element

#include <stdlib.h>

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

static void siftUp(int *h, int i) {
  while (i > 0 && h[(i - 1) / 2] > h[i]) {
    swap(&h[(i - 1) / 2], &h[i]);
    i = (i - 1) / 2;
  }
}

static void siftDown(int *h, int n, int i) {
  for (;;) {
    int min = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && h[l] < h[min])
      min = l;
    if (r < n && h[r] < h[min])
      min = r;
    if (min == i)
      return;
    swap(&h[min], &h[i]);
    i = min;
  }
}

int findKthLargest(int *nums, int numsSize, int k) {
  int *pq = malloc(k * sizeof(int)); // min-heap of the k largest
  int n = 0;

  for (int i = 0; i < numsSize; i++) {
    if (n < k) {
      pq[n] = nums[i];
      siftUp(pq, n++);
    } else if (nums[i] > pq[0]) {
      pq[0] = nums[i];
      siftDown(pq, n, 0);
    }
  }

  int res = pq[0];
  free(pq);
  return res;
}

#include <functional>
#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
  int findKthLargest(vector<int> &nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : nums) {
      if ((int)pq.size() < k)
        pq.push(x);
      else if (x > pq.top()) {
        pq.pop();
        pq.push(x);
      }
    }
    return pq.top();
  }
};

package heaps

import (
    "container/heap"
    "sort"
)

type minHeap struct{ sort.IntSlice }

func (h *minHeap) Push(x any) { h.IntSlice = append(h.IntSlice, x.(int)) }

func (h *minHeap) Pop() any {
    old := h.IntSlice
    x := old[len(old)-1]
    h.IntSlice = old[:len(old)-1]
    return x
}

func findKthLargest(nums []int, k int) int {
    pq := &minHeap{}
    for _, x := range nums {
        if pq.Len() < k {
            heap.Push(pq, x)
        } else if x > pq.IntSlice[0] {
            pq.IntSlice[0] = x
            heap.Fix(pq, 0)
        }
    }
    return pq.IntSlice[0]
}

import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : nums) {
            if (pq.size() < k) {
                pq.offer(x);
            } else if (x > pq.peek()) {
                pq.poll();
                pq.offer(x);
            }
        }
        return pq.peek();
    }
}

class MinHeap {
  constructor() {
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  top() {
    return this.data[0];
  }

  push(val) {
    const h = this.data;
    h.push(val);
    let i = h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (h[p] <= h[i]) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  }

  pop() {
    const h = this.data;
    const last = h.pop();
    if (h.length === 0) return;
    h[0] = last;
    let i = 0;
    for (;;) {
      let min = i;
      const l = 2 * i + 1,
        r = 2 * i + 2;
      if (l < h.length && h[l] < h[min]) min = l;
      if (r < h.length && h[r] < h[min]) min = r;
      if (min === i) return;
      [h[min], h[i]] = [h[i], h[min]];
      i = min;
    }
  }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const pq = new MinHeap();
  for (const x of nums) {
    if (pq.size() < k) {
      pq.push(x);
    } else if (x > pq.top()) {
      pq.pop();
      pq.push(x);
    }
  }
  return pq.top();
};

import heapq
from typing import List


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        pq: List[int] = []
        for x in nums:
            if len(pq) < k:
                heapq.heappush(pq, x)
            elif x > pq[0]:
                heapq.heapreplace(pq, x)
        return pq[0]

use std::cmp::Reverse;
use std::collections::BinaryHeap;

impl Solution {
    pub fn find_kth_largest(nums: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        let mut pq = BinaryHeap::with_capacity(k);
        for x in nums {
            if pq.len() < k {
                pq.push(Reverse(x));
            } else if let Some(mut top) = pq.peek_mut() {
                if x > top.0 {
                    *top = Reverse(x);
                }
            }
        }
        pq.peek().unwrap().0
    }
}