educative.io

Educative

Sliding window Median Problem - Remove Function

In the Remove function of the sliding window median problem, After _siftup is executed on the heap why are we doing _siftdown on the heap.

Because in python. heapq._siftup does call _siftdown , please find below the code from the heap python library.

def _siftup(heap, pos):
endpos = len(heap)
startpos = pos
newitem = heap[pos]
# Bubble up the smaller child until hitting a leaf.
childpos = 2pos + 1 # leftmost child position
while childpos < endpos:
# Set childpos to index of smaller child.
rightpos = childpos + 1
if rightpos < endpos and not heap[childpos] < heap[rightpos]:
childpos = rightpos
# Move the smaller child up.
heap[pos] = heap[childpos]
pos = childpos
childpos = 2
pos + 1
# The leaf at pos is empty now. Put newitem there, and bubble it up
# to its final resting place (by sifting its parents down).
heap[pos] = newitem
_siftdown(heap, startpos, pos)

Hi @Sharad_Kodkani
You’re right, _siftup does call _siftdown, so that line can be removed from the code.