Problem:
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.   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) Input 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$). Output 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.  Constraint  $1 \leq H \leq 500,000$  $-2,000,000,000 \leq$ value of a node $\leq 2,000,000,000$  Sample Input 1 10
4 1 3 2 16 9 10 14 8 7 Sample Output 1 16 14 10 8 7 9 3 2 4 1 Reference Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):
def maxHeapify(heap, i):
    left = (i + 1) * 2 - 1
    right = (i + 1) * 2
    largest = left if left < len(heap) and heap[left] > heap[i] else i
    largest = right if right < len(heap) and heap[right] > heap[largest] else largest
    if largest != i:
        heap[i], heap[largest] = heap[largest], heap[i]
        maxHeapify(heap, largest)

def buildMaxHeap(heap):
    for i in range(len(heap) // 2, -1, -1):
        maxHeapify(heap, i)

n = int(input())
heap = list(map(int, input().split()))
buildMaxHeap(heap)

out = ''
for key in heap:
    out += (' {}'.format(str(key)))
print(out)

Solution (Python):
global A

def max_heapfy(i):
    left = 2*i+1
    right = 2*i+2

    max_val = 0
    if left< H and A[i] < A[left]:
        max_val = left
    else:
        max_val = i

    if right<H and A[max_val] < A[right]:
        max_val = right

    if max_val != i:
        temp = A[i]
        A[i] = A[max_val]
        A[max_val] = temp
        max_heapfy(max_val)

if __name__ == '__main__':
    global H
    H = int(input())
    A = [int(i) for i in input().split()]
    for i in reversed(range(H//2)):
        max_heapfy(i)

    for a in A:
        print(" {}".format(a),end='')
    print('')

Solution (Python):
def max_heapify(A, i):
  l = i * 2
  r = l + 1
  largest = i
  if l <= H and A[l] > A[i]: largest = l
  if r <= H and A[r] > A[largest]: largest = r
  if largest != i:
    A[i], A[largest] = A[largest], A[i]
    max_heapify(A, largest)

def build_max_heap(A):
  for i in range(H // 2, 0, -1):
    max_heapify(A, i)

H = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
build_max_heap(A)

print(" " + " ".join(map(str, A[1:])))

Solution (Python):
class Heap:
    def __init__(self, L):
        self.H = len(L)
        self.heap = L
        self.heap.insert(0, 0)

    def parent(self, i):
        return i // 2

    def left(self, i):
        return 2 * i

    def right(self, i):
        return 2 * i + 1

    def maxHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        if l <= H and self.heap[l] > self.heap[i]:
            largest = l
        else:
            largest = i

        if r <= H and self.heap[r] > self.heap[largest]:
            largest = r

        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self.maxHeapify(largest)

    def buildMaxHeap(self):
        for i in range(self.H // 2, 0, -1):
            self.maxHeapify(i)


H = int(input())
L = list(map(int, input().split()))
heap = Heap(L)
heap.buildMaxHeap()
heap.heap.pop(0)
print(' ' + ' '.join([str(a) for a in heap.heap]))

Solution (Python):
H = int(input())
A = [None] + [int(i) for i in input().split()]

def maxHeapify(H, A, i):
    left = 2*i
    right = left + 1

    if left <= H and A[left] > A[i]:
        largest = left
    else: largest = i
    if right <= H and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest],A[i]
        maxHeapify(H,A,largest)

def buildmaxHeap(H,A):
    for i in range(H//2,0,-1):
        maxHeapify(H,A,i)

buildmaxHeap(H,A)

for i in A[1:]:
    print(" " + str(i), end="")
print("")

Solution (Python):
class Heap(list):
    def __init__(self, init_list = []):
        super().__init__(init_list)

    @staticmethod
    def left(i: int) -> int:
        return 2 * i + 1

    @staticmethod
    def right(i: int) -> int:
        return 2 * i + 2

    def max_heapify(self, i: int):
        l = self.left(i)
        r = self.right(i)
        H = len(self)
        
        if l < H and self[l] > self[i]:
            largest = l
        else:
            largest = i
        if r < H and self[r] > self[largest]:
            largest = r
        if largest != i:  
            
            tmp = self[i]
            self[i] = self[largest]
            self[largest] = tmp
            self.max_heapify(largest)  

    def build_max_heap(self):
        for i in range(len(self)//2, -1, -1):
            self.max_heapify(i)

n = int(input())
xs = Heap([int(i) for i in input().split()])
xs.build_max_heap()
print(" " + " ".join([str(i) for i in xs] ))

Solution (Python):
def max_heapify(A, i):
  l = i * 2
  r = l + 1
  largest = i
  if l <= H and A[l] > A[i]: largest = l
  if r <= H and A[r] > A[largest]: largest = r
  if largest != i:
    A[i], A[largest] = A[largest], A[i]
    max_heapify(A, largest)
 
def build_max_heap(A):
  for i in range(H // 2, 0, -1):
    max_heapify(A, i)
 
H = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
build_max_heap(A)
 
print(" " + " ".join(map(str, A[1:])))

Solution (Python):
import sys

def get_left(i):
    return 2 * i + 1

def get_right(i):
    return 2 * i + 2

def get_parent(i):
    return int((i - 1) / 2)

def make_heap_tree(array, i, item_num):
    left = get_left(i)
    right = get_right(i)
    largest = i
    if (left < item_num) and (array[left] > array[largest]):
        largest = left
    if (right < item_num) and (array[right] > array[largest]):
        largest = right
    if largest != i:
        tmp = array[i]
        array[i] = array[largest]
        array[largest] = tmp
        make_heap_tree(array, largest, item_num)

def main():
    size = int(sys.stdin.readline().strip())
    array = map(lambda x: int(x), sys.stdin.readline().strip().split(" "))
    for i in reversed(range(0, get_parent(size) + 1)):
        make_heap_tree(array, i, size)
    print " " + " ".join(map(lambda x: str(x), array))

if __name__ == "__main__":
    main()

Solution (Python):
def maxHeapify(A, i):
    l = 2*i + 1
    r = 2*i + 2
    if l <= H-1 and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= H-1 and A[r] > A[largest]:
        largest = r

    if largest != i:
        temp = A[i]
        A[i] = A[largest]
        A[largest] = temp
        maxHeapify(A, largest)


def buildMaxHeap(A):
    for i in range(H//2-1, -1, -1):
        maxHeapify(A, i)


if __name__ == "__main__":
    H = int(input())
    inp = list(map(int, input().split()))
    buildMaxHeap(inp)
    print(" " + " ".join(map(str, inp)))

Solution (Python):
import sys
H = input()

def main():
    A = map(int,raw_input().split())
    buildMaxHeap(A)
    for i in A:
        sys.stdout.write(" {}".format(i))
    print ""

def maxHeapify(A,i):
    l = 2*i
    r = 2*i+1
    if l <= H and A[l-1] > A[i-1]:
        largest = l
    else:
        largest = i
    if r <= H and A[r-1] > A[largest-1]:
        largest = r

    if largest != i:
        v = A[i-1]
        A[i-1] = A[largest-1]
        A[largest-1] = v
        maxHeapify(A,largest)

def buildMaxHeap(A):
    for j in range(H/2):
        i = H/2-j
        maxHeapify(A,i)


if __name__ == "__main__":
    main()

Solution (Python):
def swap(A, x, y):
    i = A[x]
    A[x] = A[y]
    A[y] = i

def left(i):
    return i * 2

def right(i):
    return i * 2 + 1

def  maxHeapify(A, i, H):
    l = left(i)
    r = right(i)
    
    if l <= H and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= H and A[r] > A[largest]:
        largest = r

    if largest != i: 
        swap(A, i, largest) 
        maxHeapify(A, largest, H) 

def buildMaxHeap(A, H):
    for i in range(int(H/2),0,-1):
        maxHeapify(A, i, H)

def main():

    """ ????????? """
    H = int(input().strip())
    A = [""]
    A.extend(list(map(int,input().split())))
    buildMaxHeap(A, H)
    print(" {}".format(" ".join(map(str,A[1:]))))

if __name__ == '__main__':
    main()

Solution (Python):
import heapq

N = int(input())
H = list(map(int, input().split()))
ans = []

a = [(-x, x) for x in H]
heapq.heapify(a)

for i in range(N):
    print(" {}".format(a[i][1]), end = "")
print()

Solution (Python):

import sys
from math import floor
sys.setrecursionlimit(100000)

N = int(input())
A = [None] + [int(n) for n in input().split()]

def max_heapify(A, i):
    l = 2 * i
    r = 2 * i + 1
    if l <= N and A[l] > A[i]:
        largest = l
    else:
        largest = i
    
    if r <= N and A[r] > A[largest]:
        largest = r
    
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

for i in range(N//2, 0, -1):
    max_heapify(A, i)

print(" " + " ".join(map(str, A[1:])))

Solution (Python):
class Node():
    def __init__(self, id, key, parent, left, right):
        self.id = id
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
    def show(self):
        print 'node %d: key = %d,' % (self.id, self.key),
        if self.parent:
            print 'parent key = %d,' % self.parent, 
        if self.left:
            print 'left key = %d,' % self.left,
        if self.right:
            print 'right key = %d,' % self.right,
        print ''

def calcParent(key):
    if key == 1:
        return None
    else:
        return data[int(key/2) - 1]

def calcLeft(key, flag=0):
    if flag == 1:
        return 2 * key
    if 2 * key < n + 1:
        return data[2 * key - 1]
    return None

def calcRight(key, flag=0):
    if flag == 1:
        return 2 * key + 1
    if 2 * key < n:
        return data[2 * key]
    return None

def maxHeapify(T, i):
    val_i, val_l, val_r = T[i].key, None, None
    if T[i].left:
        val_l = T[i*2].key
    if T[i].right:
        val_r = T[i*2+1].key
    if val_l and val_l > val_i:
        largest = val_l
    else:
        largest = val_i
    if val_r and val_r > largest:
        largest = val_r
    if largest != val_i:
        T[i].key = largest
        if T[i].parent:
            if T[int(i/2)].left == val_i:
                T[int(i/2)].left = largest
            else:
                T[int(i/2)].right = largest
        if largest == val_l:
            T[i*2].key = val_i
            T[i*2].parent = largest
            T[i].left = val_i
            T = maxHeapify(T, i*2)
        else:
            T[i*2+1].key = val_i
            T[i*2+1].parent = largest
            T[i].right = val_i
            T = maxHeapify(T, i*2+1)
    return T
        
n = int(raw_input())
data = map(int, raw_input().split())
T = {}
for i in range(n):
    this_id = i + 1
    T[this_id] = Node(i+1, data[i], calcParent(this_id), calcLeft(this_id), calcRight(this_id))
for i in range(int(n/2), 0, -1):
    T = maxHeapify(T, i)
    
print '',
for i in T.keys():
    print  T[i].key,

Solution (Python):
H = int(input())
A = list(map(int, input().split()))

def MaxHeapify(a, i):
    li, ri = 2*i+1, 2*i+2
    if li < H and a[li] > a[i]:
        largest = li
    else:
        largest  = i
        
    if ri < H and a[ri] > a[largest]:
        largest = ri
        
    if a[largest] > a[i]:
        a[i], a[largest] = a[largest], a[i]
        MaxHeapify(a, largest)

def BuildMaxHeap(a):
    for i in range(H//2, -1, -1):
        MaxHeapify(a, i)
        
BuildMaxHeap(A)

print(' ', end='')
print(*A)

Solution (Python):
H = int(input())
def maxHeapify(A, i):
    l = 2 * i + 1
    r = 2 * i + 2
    if l < H and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < H and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest)

def buildMaxHeap(A):
    for i in range(H//2 + 1, -1, -1):
        maxHeapify(A, i)

A = [int(i) for i in input().split()]
buildMaxHeap(A)
print(' ' + ' '.join(map(str,A)))

Solution (Python):
def maxHeapify(a, i):
    l = 2*i
    r = 2*i + 1
    if l <= h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r <= h and a[r] > a[largest]:
        largest = r
    
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(a, largest)

h = int(input())
n = int(0.5*h)
key = list(map(int,input().split()))
key.insert(0,0)

for i in range(n):
    j = n - i
    maxHeapify(key, j)

print("",*key[1:])

Solution (Python):



def max_Heapify(tree, n, i):
    left = (i + 1) * 2 - 1
    right = left + 1

    if left < n and tree[left] > tree[i]:
        largest = left
    else:
        largest = i

    if right < n and tree[right] > tree[largest]:
        largest = right

    if largest != i:
        tree[i], tree[largest] = tree[largest], tree[i]
        max_Heapify(tree, n, largest)


def BuildMaxHeap(tree, n):
    for i in range(n // 2 - 1, -1, -1):
        max_Heapify(tree, n, i)


if __name__ == "__main__":
    n = int(input())
    tree = [int(n) for n in input().split()]
    BuildMaxHeap(tree, n)
    print(" " + " ".join([str(n) for n in tree]))

Solution (Python):
def maxHeapify(A,i,H):
    l=2*i
    r=2*i+1

    if l<=H and A[l-1]>A[i-1]:
        largest=l
    else:
        largest=i
    if r<=H and A[r-1]>A[largest-1]:
        largest=r
    
    if largest!=i:
        A[i-1],A[largest-1]=A[largest-1],A[i-1]
        maxHeapify(A,largest,H)
        
H=int(input())
A=list(map(int,input().split()))
for i in range(H//2,0,-1):
    maxHeapify(A,i,H)
    
print(" {}".format(" ".join(map(str,A))))

Solution (Python):


def parent(i):
    return i // 2

def left(i):
    return 2*i

def right(i):
    return 2*i + 1

def maxHeapify(A, i):
    global H
    l = left(i)
    r = right(i)
    if l <= H and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= H and A[r] > A[largest]:
        largest = r

    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest)

def buildMaxHeap(A):
    for i in range(H//2, 0, -1):
        maxHeapify(A, i)


if __name__ == '__main__':

    H = int(input())
    A = [None] + [int(i) for i in input().split(" ")]

    buildMaxHeap(A)

    print(" " + " ".join(map(str, A[1:])))

Solution (Python):
H = int(input())
L = list(map(int, input().split()))
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < H and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < H and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest)
def buildMaxHeap(A):
    for i in range(H // 2, -1, -1):
        maxHeapify(A, i)
buildMaxHeap(L)
print("", *L)

Solution (Python):
H = int(input())
L = list(map(int, input().split()))
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < H and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < H and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest)
def buildMaxHeap(A):
    for i in range(H // 2, -1, -1):
        maxHeapify(A, i)
buildMaxHeap(L)
print("", " ".join(map(str, L)))

Solution (Python):
input()
A=[0]+list(map(int,input().split()))
H=len(A)
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
a=''
for s in A[1:]:a+=f' {s}'
print(a)

Solution (Python):
input()
A=[0]+list(map(int,input().split()))
H=len(A)
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
input()
A=[0]+list(map(int,input().split()))
H=len(A)
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
input()
A=[0]+list(map(int,input().split()))
H=len(A)
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
input()
A=[0]+list(map(int,input().split()))
H=len(A)
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r,g=l+1,[i,l][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 if l<H and A[i]<A[l]:g=l
 else:g=i
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 if l<H and A[i]<A[l]:g=l
 else:g=i
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 if l<H and A[i]<A[l]:g=l
 else:g=i
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 if l<H and A[i]<A[l]:g=l
 else:g=i
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 if l<H and A[i]<A[l]:g=l
 else:g=i
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 if l<H and A[i]<A[l]:g=l
 else:g=i
 if r<H and A[g]<A[r]:g=r
 if g!=i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=l if l<H and A[i]<A[l]else i
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=l if l<H and A[i]<A[l]else i
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=l if l<H and A[i]<A[l]else i
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=l if l<H and A[i]<A[l]else i
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=l if l<H and A[i]<A[l]else i
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=l if l<H and A[i]<A[l]else i
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=l if l<H and A[i]<A[l]else i
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=l if l<H and A[i]<A[l]else i
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[i]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[i]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[i]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[i]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[i]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[i]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[i]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[g]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[g]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[g]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[g]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[g]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[g]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[g]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[g]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 if r<H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 if r<H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 if r<H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 if r<H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def s(x,y):A[x],A[y]=A[y],A[x];h(y)
def h(i):
 l=2*i;r=l+1
 if r<H:
  if A[i]<A[l]:
   if A[l]<A[r]:s(i,r)
   else:s(i,l)
  elif A[i]<A[r]:s(i,r)
 elif l<H and A[i]<A[l]:s(i,l)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
H=int(input())+1
A=[0]+list(map(int,input().split()))
def s(x,y):A[x],A[y]=A[y],A[x];h(y)
def h(i):
 l=2*i;r=l+1
 if r<H:
  if A[i]<A[l]:
   if A[l]<A[r]:s(i,r)
   else:s(i,l)
  elif A[i]<A[r]:s(i,r)
 elif l<H and A[i]<A[l]:s(i,l)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

def maxheapify(a, i):
    l = i*2 + 1
    r = i*2 + 2

    if r < n:
        if a[l] > a[i]:
            largest = l
        else:
            largest = i
        if a[r] > a[largest]:
            largest = r

        if largest != i:
            memo = a[i]
            a[i] = a[largest]
            a[largest] = memo
            maxheapify(a, largest)

    elif l < n:
        if a[l] > a[i]:
            largest = l
        else:
            largest = i
        if largest != i:
            memo = a[i]
            a[i] = a[largest]
            a[largest] = memo
            maxheapify(a, largest)

for i in reversed(range(n)):
    maxheapify(a, i)

print("", *a)