Static ArrayList Q1(ArrayList input, int k){//return an ArrayList containing the

Question

Static ArrayList Q1(ArrayList input, int k){//return an ArrayList containing the k largest elements from input return null;}

Explanation / Answer

#include #include 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 buildHeap(); 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]; } // to replace root with new node x and heapify() new root void replaceMin(int x) { harr[0] = x; MinHeapify(0); } }; MinHeap::MinHeap(int a[], int size) { heap_size = size; harr = a; // store address of array } void MinHeap::buildHeap() { 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

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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