repl.it HW3- A4-Extract Max from Max Heap This is a preview. Take or import to s
ID: 3745313 • Letter: R
Question
repl.it HW3- A4-Extract Max from Max Heap This is a preview. Take or import to see all content Duer Instructions from your teacher Extracl Max Irom Max Heap this aasnment, vai will implemenr the code to ex met the max element roma henp retin ir md then rebalance the tree One way to do this is to swap the bead of the heap (ie. the max element) with the last element of the beap, remove it from the end, and then rebalance - def get prenti "Return the index of the parent of index i. return flocr((i 1," 2) 7-def get leftchil(1): One ay to get and remove the last element Return the index of tha left child of 1ndex1. eturn 1 1 xpop() 11- def get richt childi) "Return the inlex of the right child of index i." return i * 2 + 2 def is rax heop(hep): One way to get and sornove the top clement Return trUQ If the array is a rax heap . . x-pop(o) return left and right 2, 3 22 def extract nx(hesp): Your code heng Expected beharior: heap [13, 9, 12, 7, 1, 18, 5, 3] len (heap) -B extract_max(heap)13 s_mar_heap(heap) True len(heap)7 Python 3.6.1 (defoult, Dec 2815, 13:e5:11) [Gcc 4.8.2 on 1inux tract max(heap) 12 ismax_hoap(heap)rue en(heap) 6Explanation / Answer
Below is your function
def extract_max(heap):
if len(heap) > 1:
first = heap[0]
last = heap.pop()
heap[0] = last
down_heap_max(heap, 0)
return first
else:
return heap.pop()
def down_heap_max(A, i):
left = 2*i + 1
right = 2*i + 2
largest = i
if left < len(A) and A[left] > A[largest]:
largest = left
if right < len(A) and A[right] > A[largest]:
largest = right
if not largest == i:
swap(A, i, largest)
down_heap_max(A, largest)
def swap(A, a, b):
tmp = A[a]
A[a] = A[b]
A[b] = tmp
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.