K’th Smallest Element in Unsorted Array

// Simple Javascript program to find K'th smallest element

// Function to return K'th smallest element in a given array
function kthSmallest(arr, N, K)
{
    // Sort the given array
    arr.sort((a,b) => a-b);

    // Return k'th element in the sorted array
    return arr[K - 1];
}

// Driver program to test above methods
    let arr = [12, 3, 5, 7, 19];
    let N = arr.length, K = 2;
    console.log("K'th smallest element is " + kthSmallest(arr, N, K));

// Function to find the kth smallest array element
function kthSmallest(arr, K) {
    // Create a max heap (priority queue)
    let pq = new MaxHeap();

    // Iterate through the array elements
    for (let i = 0; i < arr.length; i++) {
        // Push the current element onto the max heap
        pq.push(arr[i]);

        // If the size of the max heap exceeds K, remove the largest element
        if (pq.size() > K)
            pq.pop();
    }

    // Return the Kth smallest element (top of the max heap)
    return pq.top();
}

// MaxHeap class definition
class MaxHeap {
    constructor() {
        this.heap = [];
    }

    push(val) {
        this.heap.push(val);
        this.heapifyUp(this.heap.length - 1);
    }

    pop() {
        if (this.heap.length === 0) {
            return null;
        }
        if (this.heap.length === 1) {
            return this.heap.pop();
        }

        const root = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown(0);

        return root;
    }

    top() {
        if (this.heap.length === 0) {
            return null;
        }
        return this.heap[0];
    }

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

    heapifyUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] >= this.heap[index]) {
                break;
            }
            this.swap(parentIndex, index);
            index = parentIndex;
        }
    }

    heapifyDown(index) {
        const leftChildIndex = 2 * index + 1;
        const rightChildIndex = 2 * index + 2;
        let largestIndex = index;

        if (
            leftChildIndex < this.heap.length &&
            this.heap[leftChildIndex] > this.heap[largestIndex]
        ) {
            largestIndex = leftChildIndex;
        }

        if (
            rightChildIndex < this.heap.length &&
            this.heap[rightChildIndex] > this.heap[largestIndex]
        ) {
            largestIndex = rightChildIndex;
        }

        if (index !== largestIndex) {
            this.swap(index, largestIndex);
            this.heapifyDown(largestIndex);
        }
    }

    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
}

// Driver's code:
const arr = [10, 5, 4, 3, 48, 6, 2, 33, 53, 10];
const K = 4;

// Function call
console.log("Kth Smallest Element is: " + kthSmallest(arr, K));

// Function to find the kth smallest element in an array
function kthSmallest(arr, k) {
    // First, find the maximum element in the array
    let maxElement = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > maxElement) {
            maxElement = arr[i];
        }
    }

    // Create an array to store the frequency of each element in the input array
    let freq = new Array(maxElement + 1).fill(0);
    for (let i = 0; i < arr.length; i++) {
        freq[arr[i]]++;
    }

    // Keep track of the cumulative frequency of elements in the input array
    let count = 0;
    for (let i = 0; i <= maxElement; i++) {
        if (freq[i] !== 0) {
            count += freq[i];
            if (count >= k) {
                // If we have seen k or more elements, return the current element
                return i;
            }
        }
    }
    return -1; // kth smallest element not found
}

// Driver code
const arr = [12, 3, 5, 7, 19];
const k = 2;
console.log(`The ${k}th smallest element is ${kthSmallest(arr, k)}`);