output_description: Print values of nodes in the max-heap in order of their id (from $1$ to $H$).
  _Print a single space character before each value._
input_description: In the first line, an integer $H$ is given. In the second line, $H$ integers
  which represent elements in the binary heap are given in order of node id
  (from $1$ to $H$).
attempt: class MaxHeap:
      def __init__(self):
          self.heap = []
          self.length = 0
  
      def __str__(self):
          return " " + " ".join(str(n) for n in self.heap)
  
      def up_insert(self, key):
          self.heap.append(key)
          self._upheap()
          self.length += 1
  
      def down_insert(self, key):
          self.heap.append(key)
          self.length += 1
          for i in range(self.length // 2, -1, -1):
              self._downheap(i)
  
      def down_many_insert(self, key):
          self.heap.extend(key)
          self.length += len(key)
          for i in range(self.length // 2, -1, -1):
              self._downheap(i)
  
      def _upheap(self):
          index = self.length - 1
          while True:
              parent_index = (index - 1) // 2
              if parent_index < 0 or self.heap[parent_index] >= self.heap[index]:
                  break
              self.heap[parent_index], self.heap[index] = (
                  self.heap[index],
                  self.heap[parent_index],
              )
              index = parent_index
  
      def _downheap(self, index):
          while True:
              child_index_left, child_index_right = index * 2 + 1, index * 2 + 2
              # print(index, child_index_left, child_index_right)
              if child_index_left >= self.length:
                  break
              elif (
                  child_index_right >= self.length
                  or self.heap[child_index_left] > self.heap[child_index_right]
              ) and self.heap[index] < self.heap[child_index_left]:
                  self.heap[index], self.heap[child_index_left] = (
                      self.heap[child_index_left],
                      self.heap[index],
                  )
                  index = child_index_left
              elif (
                  child_index_right < self.length
                  and self.heap[child_index_left] < self.heap[child_index_right]
              ) and self.heap[index] < self.heap[child_index_right]:
                  self.heap[index], self.heap[child_index_right] = (
                      self.heap[child_index_right],
                      self.heap[index],
                  )
                  index = child_index_right
              else:
                  break
  
  
  a = MaxHeap()
  length = int(input())
  t = [int(n) for n in input().split(" ")]
  a.down_many_insert(t)
  print(a)
  
problem_description: Maximum Heap
  
  A binary heap which satisfies max-heap property is called max-heap. In a max-
  heap, for every node $i$ other than the root, $A[i] \leq A[parent(i)]$, that
  is, the value of a node is at most the value of its parent. The largest
  element in a max-heap is stored at the root, and the subtree rooted at a node
  contains values no larger than that contained at the node itself.
  
  Here is an example of a max-heap.
  
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ALDS1_9_B_1)  
  
  Write a program which reads an array and constructs a max-heap from the array
  based on the following pseudo code.
  
  $maxHeapify(A, i)$ move the value of $A[i]$ down to leaves to make a sub-tree
  of node $i$ a max-heap. Here, $H$ is the size of the heap.
  
      
      
      1  maxHeapify(A, i)
      2      l = left(i)
      3      r = right(i)
      4      // select the node which has the maximum value
      5      if l ≤ H and A[l] > A[i]
      6          largest = l
      7      else 
      8          largest = i
      9      if r ≤ H and A[r] > A[largest]
      10         largest = r
      11
      12     if largest ≠ i　// value of children is larger than that of i
      13         swap A[i] and A[largest]
      14         maxHeapify(A, largest) // call recursively
      
  
  The following procedure buildMaxHeap(A) makes $A$ a max-heap by performing
  maxHeapify in a bottom-up manner.
  
      
      
      1 buildMaxHeap(A)
      2    for i = H/2 downto 1
      3        maxHeapify(A, i)
samples: [{"input": "10\n    4 1 3 2 16 9 10 14 8 7", "output": "16 14 10 8 7 9 3 2 4 1"}]