Kth smallest element- can't create array more than the size of k

Question

I have implemented an algorithm that solves the problem of finding the k^th smallest element in an unsorted array. I have used the heap structure, and optimized the code by relying on this formula,

      k₁ = n - k + 1

k₁ being the k₁^th largest element, so I go for the smaller of k and k₁.

Still, I couldn't pass the time limit error on an online judge. I don't know if there will be any further more better complexity having in mind that I have to create an array no more than the size of k; maybe less than k possible? Or there is another way to solve this problem other than using the heap structure.

1 <= k <= n <= 10⁵

The code:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

void minHeapify(int arr[], int n, int i)
{
    int largest = i; // Initialize largest as root 
    int l = 2 * i + 1; // left = 2*i + 1 
    int r = 2 * i + 2; // right = 2*i + 2 

    if (l < n && arr[l] < arr[largest])
        largest = l;

    if (r < n && arr[r] < arr[largest])
        largest = r;

    if (largest != i) {
        swap(arr[i], arr[largest]);

        minHeapify(arr, n, largest);
    }
}

void maxHeapify(int arr[], int n, int i)
{
    int smallest = i; // Initialize largest as root 
    int l = 2 * i + 1; // left = 2*i + 1 
    int r = 2 * i + 2; // right = 2*i + 2 

    if (l < n && arr[l] > arr[smallest])
        smallest = l;

    if (r < n && arr[r] > arr[smallest])
        smallest = r;

    if (smallest != i) {
        swap(arr[i], arr[smallest]);

        maxHeapify(arr, n, smallest);
    }
}

void buildMinHeap(int a[], int n) {
    for (int i = n / 2; i >= 0; i--)
        minHeapify(a, n, i);
}

void buildMaxHeap(int a[], int n) {
    for (int i = n / 2; i >= 0; i--)
        maxHeapify(a, n, i);
}

int kthsmallest(int minHeap[], int k, int n) {
    int i, temp;
    for (i = 0; i < k; i++)
        cin >> minHeap[i];

    buildMaxHeap(minHeap, k);

    for (i = k; i < n; i++)
    {
        cin >> temp;
        if (temp < minHeap[0])
        {
            minHeap[0] = temp;
            maxHeapify(minHeap, k, 0);
        }
    }
    return minHeap[0];
}

int kthlargest(int minHeap[], int k, int n) {    
    int i, temp;
    for (i = 0; i < k; i++)
        cin >> minHeap[i];

    buildMinHeap(minHeap, k);

    for (i = k; i < n; i++)
    {
        cin >> temp;
        if (temp > minHeap[0])
        {
            minHeap[0] = temp;
            minHeapify(minHeap, k, 0);
        }
    }
    return minHeap[0];    
}

int main() {//kth smallest element    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int n, k, k1;
    cin >> n >> k;
    k1 = n - k + 1;//kth smallest element is the same as k1th largest element

    if (k < k1) {
        int *minHeap = new int[k];
        cout << kthsmallest(minHeap, k, n);
    }    
    else {
        int *minHeap = new int[k1];
        cout << kthlargest(minHeap, k1, n);
    }
    return 0;
}

Please if you could help finding a better time complexity?

Problem:

Find the k^th largest element of an array

Memory limit: 256 MBs
Time limit: 1 s
Input: input.txt
Output: output.txt

---

Task:

You are given an array of n integers and a natural k.
You have to find the k^th largest element of the array.
You can't create array consisting of more than k elements.

Input:

The first line contains a natural n (1 ≤ n≤10⁵) – the quantity of elements of the array, and the natural k.
The second line contains n numbers – the elements of the array.

Output:

The k^th largest element of the array.

Example:

Input        | Output
-------------+-----------
6 2          | 7
7 4 6 3 9 1  | 

Answer 1

The time complexity is optimal, but you can make your code a tiny bit more efficient:

• Don't use recursion, but an iterative solution
• Don't use swap, but keep the original value in memory while copying child values to their parents and only store the initial value once you have reached the appropriate slot.
• Don't perform twice 2 * i: the other child node is just the next one.
• Let the heapify functions take an extra argument, which can be either the current value at index i, or the replacement value for it. This saves one assignment.

Here is how that would look for two heapify functions:

void minHeapify(int arr[], int n, int i, int key) { // add key as parameter
    while (true) { // iterative
        int child = 2 * i + 1; // do this only for left child, and limit number of variables
        if (child+1 < n && arr[child] > arr[child+1]) // get child with least value
            child++; // the right child is just one index further
        if (child >= n || key <= arr[child]) break;
        arr[i] = arr[child]; // don't swap, just copy child value to parent
        i = child; // move down
    }
    arr[i] = key; // finally put the original value in the correct place
}

void maxHeapify(int arr[], int n, int i, int key) { // add key as parameter
    while (true) { // iterative
        int child = 2 * i + 1; // do this only for left child, and limit number of variables
        if (child+1 < n && arr[child] < arr[child+1]) // get child with greatest value
            child++; // the right child is just one index further
        if (child >= n || key >= arr[child]) break;
        arr[i] = arr[child]; // don't swap, just copy child value to parent
        i = child; // move down
    }
    arr[i] = key; // finally put the original value in the correct place
}

void buildMinHeap(int a[], int n) {
    for (int i = n / 2; i >= 0; i--)
        minHeapify(a, n, i, a[i]); // pass a[i] also
}

void buildMaxHeap(int a[], int n) {
    for (int i = n / 2; i >= 0; i--)
        maxHeapify(a, n, i, a[i]); // pass a[i] also
}

int kthsmallest(int heap[], int k, int n) {
    int i, temp;
    for (i = 0; i < k; i++)
        cin >> heap[i];

    buildMaxHeap(heap, k);

    for (i = k; i < n; i++) {
        cin >> temp;
        if (temp < heap[0])
            maxHeapify(heap, k, 0, temp); // pass temp
    }
    return heap[0];
}

int kthlargest(int heap[], int k, int n) {
    int i, temp;
    for (i = 0; i < k; i++)
        cin >> heap[i];

    buildMinHeap(heap, k);

    for (i = k; i < n; i++) {
        cin >> temp;
        if (temp > heap[0])
            minHeapify(heap, k, 0, temp); // pass temp
    }
    return heap[0];
}

In main function you could make a special case for when k == 1 or k == n, so no heap is needed, just min() or max().

One strange thing is that the challenge you link to speaks of "k^th largest" while you speak of "k^th smallest". Maybe you mixed up.

So here is the code when the job is to return the k^th smallest. But please check the challenge whether you should not have done it for k^th largest:

int main() {//kth smallest element    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int n, k, k1;
    cin >> n >> k;
    k1 = n - k + 1;//kth smallest element is the same as k1th largest element

    if (k == 1) {
        int curr, next;
        cin >> curr;
        for (int i = 1; i < n; i++) {
            cin >> next;
            curr = min(curr, next);
        }
        cout << curr;
    } else if (k1 == 1) {
        int curr, next;
        cin >> curr;
        for (int i = 1; i < n; i++) {
            cin >> next;
            curr = max(curr, next);
        }
        cout << curr;
    } else if (k < k1) {
        int *heap = new int[k];
        cout << kthsmallest(heap, k, n);
    } else {
        int *heap = new int[k1];
        cout << kthlargest(heap, k1, n);
    }
    return 0;
}

Answer 2

You're making the assumption that using a smaller heap is always the best choice. You might want to re-think that.

For example, imagine you want to select the 96th smallest number from a list of 100. If you use a heap of size 96, then you'll do:

1. Build a heap with 96 items. buildHeap is O(n), and in this case n is 96.
2. Do up to 4 insertions into a heap of 96 items. That'll be 4*log(96).

If you use a heap of size 4, then you'll do:

1. Build a heap with 4 items.
2. Do up to 96 insertions into a heap of 4 items. That'll be 96*log(4).

The first option is 96 + 4*log(96). The base-2 log of 96 is about 6.58. So the insertions will cost 26.32, for a total of 122.32.

The second option, with the smaller heap, is 4 + 96*log(4). log(4) is 2, so you end up with 4 + 196, or a total of 196.

The smaller heap is a big loser here.

In general, you want to use the larger heap when (k + (n-k)*log(k)) < ((n-k) + k*log(n-k)).

Also:

The real-world running time of the heap selection algorithm is kind of sensitive to the order in which items are presented. For example, if you're looking for 1000th smallest number in an array of 100,000, it's going to run much faster if the array is in ascending order than if it's in descending order. The reason?

Because in the ascending case, you build your initial heap with the first 1,000 items and then you never have to modify the heap again because there is none of the following items are smaller than the largest item on the heap.

But if the array is in descending order, then every item you look at will be smaller than the largest item on the heap, which means you'd be doing a heap insertion for all 99,000 remaining items.

Imagine how your code would perform if one of the test cases is a large array in descending order.

Unless you've already proven that your way of selecting which heap size to use is clearly better, you might want to consider just going with "select kth smallest," using a maxheap of size k, regardless.