Lecture Notes 13 Apr 2018

class Heap (object):
  def __init__ (self):
    self.heap = []

  # return the size of the heap
  def get_size (self):
    return len (self.heap)

  # return if the heap is empty
  def is_empty (self):
    return (self.get_size() == 0)

  # get index of left child
  def lchild_idx (self, idx):
    new_idx = 2 * idx + 1
    if (new_idx >= len(self.heap)):
      new_idx = -1
    return new_idx

  # get index of right child
  def rchild_idx (self, idx):
    new_idx = 2 * idx + 2
    if (new_idx >= len(self.heap)):
      new_idx = -1
    return new_idx

  # get index of parent
  def parent_idx (self, idx):
    new_idx = (idx - 1 ) // 2
    if (idx == 0):
      new_idx = -1
    return new_idx

  # move a node up from the bottom to its rightful position
  def percolate_up (self, idx):
    node_val = self.heap[idx]
    parent = parent_idx (idx)
    while ((idx > 0) and (self.heap[parent] < node_val)):   
      self.heap[idx] = self.heap [parent]
      idx = parent
      parent = parent_idx (idx)
    self.heap[idx] =  node_val


  # move a node down from the top to its rightful position
  def percolate_down (self, idx):
    node_val = self.heap[idx]
    num_elements = self.get_size()
    while (idx < num_elements // 2):
      left_child = lchild_idx (idx)
      right_child = rchild_idx (idx)
      if ((right_child > -1) and (self.heap[left_child] > self.heap[right_child])):
        larger_child = left_child
      else:
        larger_child = right_child
      if (node_val >= self.heap[larger_child]):
        break;
      self.heap[idx] = self.heap[larger_child]
      idx = larger_child
    self.heap[idx] = node_val

  # make a heap of a list
  def make_heap (self, idx):
    num_elements = self.get_size()
    if (idx > ((num_elements // 2) - 1)):
      return
    right_child = rchild_idx (idx)
    if (right_child > -1):
      make_heap (right_child)
    make_heap (lchild_idx(idx))
    percolate_down (idx)

  # insert an element in the heap
  def insert (self, val):
    self.heap.append (val)
    new_pos = self.get_size() - 1
    # percolate the new element up
    percolate_up (new_pos)

  # remove the root or the max element in the heap
  def remove (self):
    root = self.heap[0]
    self.heap[0] = self.heap[-1]
    self.heap.pop()
    percolate_down (0)
    return root