Write pseudo code using a heap to find the k th smallest element in a set of n e

Question

Write pseudo code using a heap to find the kth smallest element in a set of n elements in O(n + k log n) time.

Explanation / Answer

bool Example::min_heap_select(long k, long & kth_smallest) const { //duplicate test group (thanks, const!) Example test = Example(*this); //variable delcaration and initlization int n = test._total ; int i; //Heapifying stage (THIS WORKS CORRECTLY) for (i = n/2; i >= 0; i--) { //allows for heap construction test.percolate_down_protected(i, n); }//for //Delete min phase (THIS DOESN'T WORK) for(i = n-1; i >= (n-k+1); i--) { //deletes the min by swapping elements int tmp = test._group[0]; test._group[0] = test._group[i]; test._group[i] = tmp; //resumes perc down test.percolate_down_protected(0, i); }//for //IDK WHAT TO RETURN kth_smallest = test._group[0]; void Example::percolate_down_protected(long i, long n) { //variable declaration and initlization: int currPos, child, r_child, tmp; currPos = i; tmp = _group[i]; child = left_child(i); //set a sentinel and begin loop (no recursion allowed) while (child n ) && (_group[r_child] >= _group[child])) { child = r_child; } //find the correct spot if (tmp

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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