(IN JAVA PLEASE. ANY FORM OF C IS OKAY TOO. OR EVEN PSEUDOCODE) Problem: Given a

Question

(IN JAVA PLEASE. ANY FORM OF C IS OKAY TOO. OR EVEN PSEUDOCODE)

Problem: Given an (unsorted) array of $n$ elements, return the largest
$k$ elements.

There is one obvious way to do this: sort and retrieve the top $k$.
Since we can sort in $n log n$ this is not bad. Can we do better?
Yes, we can do this in $n log k$ using a heap. Your task is to
implement these two approaches and run experiments to contrast the
'real' runtime. Of course, you must contrast equivalent
implementation, so your own sort (either merge, heap or quick) and
your own heap. Clearly it would be good to use heap sort so you can
re-use the heap structure, but that is entirely up to you.


Submit your code, your experiments in a table or plot form, and a
non-trivial *conclusion*.

Explanation / Answer

CODE FOR SORT AND RETRIEVE:

#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[]) {
int array[100];

for (int i = 0; i < 100; i++) {
array[i] = i;
}

std::sort(array,array+100);
std::reverse(array,array+100);

  

for(int i =0; i<50;i++)
cout<<array[i]<<' ';
  
return 0;
}

CODE FOR SOLUTION USING HEAP:

#include<iostream>
#include<climits>
using namespace std;

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

class MaxHeap
{
int *harr;
int capacity;
int heap_size;
public:
MaxHeap(int size);
void buildHeap();
void MaxHeapify(int 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 extractMax();
int getMax() { return harr[0]; }
void insertKey(int k);
void replaceMax(int x) { harr[0] = x; MaxHeapify(0); }
};

MaxHeap::MaxHeap(int size)
{
heap_size = 0;
capacity = size;
harr = new int[size];
}
  

int MaxHeap::extractMax() {
if (heap_size == 0)
return INT_MAX;

int root = harr[0];

if (heap_size > 1)
{
harr[0] = harr[heap_size-1];
MaxHeapify(0);
}
heap_size--;
  
return root;
}

void MaxHeap::MaxHeapify(int i)
{
int l = left(i);
int r = right(i);
int largest = i;
if (l < heap_size && harr[i] < harr[l])
largest = l;
if (r < heap_size && harr[largest] < harr[r] )
largest = r;
if (largest != i)
{
swap(&harr[i], &harr[largest]);
MaxHeapify(largest);
}
}

void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}

void MaxHeap::insertKey(int k)
{
if (heap_size == capacity)
{
cout << " Overflow: Could not insertKey ";
return;
}

heap_size++;
int i = heap_size - 1;
harr[i] = k;

while (i != 0 && harr[parent(i)] < harr[i])
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}

int main() {
MaxHeap a(100);
for (int i; i < 100; i++) {
a.insertKey(i);
}

for(int i =0; i<50;i++)
cout<<a.extractMax()<<' ';

return 0;
}

Conclusion: As from above table, it can be clearly seen that sorting and then getting first K largest elements take significantly larger time than heap method and this difference increases as we move to much larger values.

Experiment :Printing first k/2 largest elements from size of k input. Size of input Time taken Using Soritng Time taken Using Heap 10000 0.51s 0.01s 30000 4.02s 0.05s 60000 16.10s 0.06s 80000 28.52s 0.07s

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.