Heap example

.py

def parent_index(i):
  return (i-1)//2
def lchild_index(i):
  return i*2+1
def rchild_index(i):
  return i*2+2

# max_min==1 means a max-heap. -1 means a min-heap.
# right means the rightmost index (not the length)
def recursive_heapify(list, i, right, max_min=1):
  if i==0:
      return  # do nothing at the root node
  pindex = parent_index(i)
  if max_min==1:
    if list[i] > list[pindex]:  # If child > parent, swap
      list[i], list[pindex] = list[pindex], list[i]
      recursive_heapify(list, pindex, right, max_min)
  else:
    if list[i] < list[pindex]:  # If parent > child, swap
      list[i], list[pindex] = list[pindex], list[i]
      recursive_heapify(list, pindex, right, max_min)
      
# right means the rightmost index (not the length)
def build_heap(list, right, max_min=1):
  for i in range(1, right+1):  # heapify except the root node
    recursive_heapify(list, i, right, max_min)