Data-structures 03

1a

1b

2

class Node:
  key: int
  size: int   # number of nodes in the tree with this Node as a root
  sum: int    # sum of all keys in the tree with this Node as a root
  left: Node
  right: Node

func less_than(root, a):
  sum = 0
  size = 0
  while root != null:
    // if root is less than range
    // then root and left subtree are less-than-range
    // and we continue to root.right
    if root.key < a:
      if root.left ! null:
        sum += root.left.sum
        size += root.left.size
      sum += node.key
      size += 1
      root = root.right
    else:
      // otherwise node and node.right in [a, b], continue to node.left
      root = root.left
  return sum, size
 
func greater_than(root, b):
  sum = 0
  size = 0
  while root != null:
    // if root is greater than range
    // then root and right subtree are greater-than-range
    // and we continue to root.left
    if root.key > b:
      if root.right ! null:
        sum += root.right.sum
        size += root.right.size
      sum += node.key
      size += 1
      root = root.left
    else:
      // otherwise node and node.left in [a, b], continue to node.right
      root = root.right
  return sum, size

func average_in_range(root, a, b):
  while root != null:
    if root.key < a:
      root = root.right
    elif root.key > b:
      root = root.left
    else:
      break
  if root == null:
    return null
  sum = root.sum
  size = root.size
  left_sum, left_size = less_than(root, a)
  right_sum, right_size = greater_than(root, b)
  sum -= left_sum
  sum -= right_sum
  size -= left_size
  size -= right_size
  return sum / size

3a

3b

4

5

func k_min(H, n, k):
  L = array[k]
  Q = new_min_heap(k)              // allocate a new heap for k elements
  insert((min(H), 0), Q)
  for i in [0, k-1]:
    m, idx = delete_min(Q)         // pop the next minimum-candidate
    L[i] = m                       // add minimum candidate to L
    if 2*idx + 1 < n:              // Add left and right children to Q
      insert((H[2*idx + 1], 2*idx + 1), Q)
	if 2*idx + 2 < n:
  	  insert((H[2*idx + 2], 2*idx + 2), Q)
  return L