[solved]-Translate Pseudocode C Algorithm Must Function Key Formulas Left Child Lc 2 Parent 1right Q39017081

Translate the pseudocode into C++. The algorithm must be afunction.

Key formulas:left child (lc) = 2 * parent + 1right child (rc) = 2 * parent + 2parent (p) = (child – 1) / 2ReHeapUp:// Inputs: heap to rebuild, bottom, top// Complexity: O(logn) i <- bottom WHILE i =/= top: p <- (i – 1) / 2 IF heap[i] > heap[p]: swap heap[p], heap[i] i <- p Enqueue:// Inputs: heap, bottom, value to add to heap IF NOT full: bottom <- bottom + 1 heap[bottom] <- value ReHeapUp[heap] ReHeapDown// Inputs: heap, top, bottom// Complexity: O(logn)p <- top WHILE p < bottom: lc <- 2p + 1 rc <- 2p + 2 IF lc <= bottom: IF lc = bottom: bc <- lc ELSE: IF heap[lc] > heap[rc]: bc <- lc ELSE: bc <- rc ELSE: QUIT IF heap[p] < heap[bc]: swap heap[p], heap[bc] p <- bc ELSE: Quit HeapSort// Inputs: the array, h, to sort and it’s size, s// Complexity: O(nlogn)// build the heap: O(n/2) => O(n)i <- s / 2 – 1WHILE i >= 0: ReHeapDown(h, i, s-1) i <- i – 1// now sort the heap: ReHeapDown, O(logn), called n times => O(nlogn)i <- b – 1WHILE i >= 0: swap h[0] and h[i] i <- i – 1 ReHeapDown(h, 0, i)Note: O(nlogn) + O(n) => O(nlogn + n) => O(nlogn)We can drop the + n because nlogn is the biggest term.Here’s an implementation:Where h is the array storing the heap, andb is the number of elements in the array.void HeapSort(int h[], int b){ // build heap int i = b / 2 – 1; // finds the last element with children. while(i >= 0) { ReHeapDown(h, i, b-1); i–; } // now, sort i = b – 1; while(i >= 0) { swap(h[0], h[i]); i–; ReHeapDown(h, 0, i); }}

Expert Answer

---

Answer to Translate the pseudocode into C++. The algorithm must be a function. Key formulas: left child (lc) = 2 * parent + 1 righ… . . .