Give an algorithm using the techniques and data structures y

Give an algorithm using the techniques and data structures you have seen in the course so far, for the following problem: the input is an array A of size n of integers, find the k largest elements of A and return them. Your algorithm must run in O(n + k log n). Explain your algorithm and analyze its running time. What is the largest value of k for which your algorithm is still linear in n?

Solution

#include<iostream>

#include<climits>

using namespace std;

// Prototype of a utility function to swap two integers

void swap(int *x, int *y);

// A class for Min Heap

class MinHeap

{

    int *harr; // pointer to array of elements in heap

    int capacity; // maximum possible size of min heap

    int heap_size; // Current number of elements in min heap

public:

    MinHeap(int a[], int size); // Constructor

    void MinHeapify(int i); //To minheapify subtree rooted with index i

    int parent(int i) { return (i-1)/2; }

    int left(int i) { return (2*i + 1); }

    int right(int i) { return (2*i + 2); }

    int extractMin(); // extracts root (minimum) element

    int getMin() { return harr[0]; } // Returns minimum

};

MinHeap::MinHeap(int a[], int size)

{

    heap_size = size;

    harr = a; // store address of array

    int i = (heap_size - 1)/2;

    while (i >= 0)

    {

        MinHeapify(i);

        i--;

    }

}

// Method to remove minimum element (or root) from min heap

int MinHeap::extractMin()

{

    if (heap_size == 0)

        return INT_MAX;

    // Store the minimum vakue.

    int root = harr[0];

    // If there are more than 1 items, move the last item to root

    // and call heapify.

    if (heap_size > 1)

    {

        harr[0] = harr[heap_size-1];

        MinHeapify(0);

    }

    heap_size--;

    return root;

}

// A recursive method to heapify a subtree with root at given index

// This method assumes that the subtrees are already heapified

void MinHeap::MinHeapify(int i)

{

    int l = left(i);

    int r = right(i);

    int smallest = i;

    if (l < heap_size && harr[l] < harr[i])

        smallest = l;

    if (r < heap_size && harr[r] < harr[smallest])

        smallest = r;

    if (smallest != i)

    {

        swap(&harr[i], &harr[smallest]);

        MinHeapify(smallest);

    }

}

// A utility function to swap two elements

void swap(int *x, int *y)

{

    int temp = *x;

    *x = *y;

    *y = temp;

}

// Function to return k\'th smallest element in a given array

int kthSmallest(int arr[], int n, int k)

{

    // Build a heap of n elements: O(n) time

    MinHeap mh(arr, n);

    // Do extract min (k-1) times

    for (int i=0; i<k-1; i++)

        mh.extractMin();

    // Return root

    return mh.getMin();

}

The largest value of k for which the algorithm is linear in n is: 1.