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):
class Heap:
    def __init__(self, a = []):
        self.h = a
        self.n = len(a)


    def parent(self, i): 
        return i // 2
    def left(self, i):
        return i * 2
    def right(self, i):
        return i * 2 + 1
    def max_heapify(self, i):
        l = self.left(i)
        r = self.right(i)

        if l <= self.n and self.h[l-1] > self.h[i-1]:
            largest = l
        else:
            largest = i
        if r <= self.n and self.h[r-1] > self.h[largest-1]:
            largest = r
        if largest != i: 
            self.h[i-1], self.h[largest-1] = self.h[largest-1], self.h[i-1]
            self.max_heapify(largest)
    def build_max_heap(self):
        for i in range((self.n // 2), 0, -1):
            self.max_heapify(i)

heap = Heap()
heap.n = int(input())
heap.h = list(map(int, input().split()))
heap.build_max_heap()
print("", *heap.h)

Solution (Python):
class Heap:
    def __init__(self, nodes):
        self._nodes = nodes
        self.size = len(nodes)

    def max_heapify(self):
        def _max_heapify(i):
            left = (i+1) * 2 - 1
            right = (i+1) * 2
            if left < self.size and self._nodes[left] > self._nodes[i]:
                largest = left
            else:
                largest = i

            if right < self.size and self._nodes[right] > self._nodes[largest]:
                largest = right

            if largest > i:
                self._nodes[i], self._nodes[largest] = \
                        self._nodes[largest], self._nodes[i]
                _max_heapify(largest)

        for i in reversed(range(self.size//2)):
            _max_heapify(i)

    def __iter__(self):
        self.cur = 0
        return self

    def __next__(self):
        if self.cur >= self.size:
            raise StopIteration
        node = self._nodes[self.cur]
        self.cur += 1

        return node

    @classmethod
    def create(cls, li):
        heap = cls(li[:])
        heap.max_heapify()
        return heap


def run():
    _ = int(input())

    nodes = [int(i) for i in input().split()]
    heap = Heap.create(nodes)

    s = ''
    for node in heap:
        s += ' {}'.format(node)

    print(s)


if __name__ == '__main__':
    run()

Solution (Python):
n = int(input())
a = [0] + list(map(int, input().split()))
def max_heapify(a, i):
    global n
    l = 2 * i
    r = 2 * i + 1
    largest = l if l <= n and a[l] > a[i] else i
    if r <= n and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[largest], a[i] = a[i], a[largest]
        max_heapify(a, largest)

for i in range(int(n / 2), 0, -1):
    max_heapify(a, i)
    
print(" " + " ".join(map(str, a[1:])))

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

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

    if largest != i:
        H[i], H[largest] = H[largest], H[i]
        max_heapify(largest)

def print_elements(lst):
    for ele in lst:
        print(' {}'.format(ele), end='')
    print('')

for i in range(int(n/2), -1, -1):
    max_heapify(i)

print_elements(H)

Solution (Python):
from collections import deque

class PriorityQueue:
    def __init__(self):
        self.nodes = []

    def max_heapify(self, i):
        if i >= len(self.nodes): return
        left, right = (i+1)*2-1, (i+1)*2

        largest = i
        if left < len(self.nodes) and self.nodes[i] < self.nodes[left]: largest = left
        if right < len(self.nodes) and self.nodes[largest] < self.nodes[right]: largest = right

        if largest != i:
            self.nodes[i], self.nodes[largest] = self.nodes[largest], self.nodes[i]
            self.max_heapify(largest)

    def print_element(self):
        for node in self.nodes:
            print('', node, end='')
        print('')

n = int(input())
A = list(map(int, input().split(' ')))

pq = PriorityQueue()
pq.nodes = A

for i in range((n-1)//2, -1, -1):
    pq.max_heapify(i)

pq.print_element()

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

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

    if largest != i:
        H[i], H[largest] = H[largest], H[i]
        max_heapify(largest)

def print_elements(lst):
    for ele in lst:
        print(' {}'.format(ele), end='')
    print('')

for i in range(int(n/2), -1, -1):
    max_heapify(i)

print_elements(H)

Solution (Python):
def maxHeapify(i, node_list):
    n = len(node_list)
    if 2*i+1 < n and node_list[2*i+1] > node_list[i]:
        i_largest = 2*i+1
        
    else:
        i_largest = i
    if 2*i+2 < n and node_list[2*i+2] > node_list[i_largest]:
        i_largest = 2*i+2
        

    if i_largest != i:
        node_list[i], node_list[i_largest] = node_list[i_largest], node_list[i]
        maxHeapify(i_largest, node_list)




n = int(input())
node_list = [int(i) for i in input().split()]
for i in range(n//2, -1, -1):
    maxHeapify(i, node_list)
print(' ' + ' '.join([str(node) for node in node_list]))

Solution (Python):

H = int(input())
ary = [int(_) for _ in input().split()]


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

    if largest != i:
        ary[i - 1], ary[largest - 1] = ary[largest - 1], ary[i - 1]
        max_heapify(ary, largest)


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


build_max_heap(ary)
print(' ', end='')
print(*ary)

Solution (Python):

"""
Created on Sat Jun  9 13:21:18 2018
ALDS1-9b
@author: maezawa
"""
import math

h = int(input())
a = list(map(int,input().split()))

def parent(node):
    return math.floor(node/2)

def left(node):
    return 2*node

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

def max_heapify(a, i):
    l = left(i)
    r = right(i)
    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]
        max_heapify(a, largest)

def build_max_heap(a):
    for i in list(range(1,h//2+1))[::-1]:
        max_heapify(a, i)
        
        
build_max_heap(a)

for i in range(h):
    print(' {}'.format(a[i]),end = '')
print()

Solution (Python):
def max_heapify(a, i):
    h = len(a)
    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:
        tmp = a[i - 1]
        a[i - 1] = a[largest - 1]
        a[largest - 1] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2, 0, -1):
        max_heapify(a, i)


def print_list_split_whitespace(a):
    s = ""
    for x in a:
        s += " " + str(x)
    print(s)


h = int(input())
heap = [int(x) for x in input().split()]

build_max_heap(heap)

print_list_split_whitespace(heap)

Solution (Python):

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

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:
        A[i-1], A[largest-1] = A[largest-1], A[i-1]
        maxHeapify(A,largest)

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

buildMaxHeap(A)
A = " " + " ".join([str(num) for num in A])
print(A)

Solution (Python):
import sys

def parent(i, n):
    tmp = i/2
    if tmp <=0 or tmp>=n: return None
    else: return tmp

def left(i, n):
    tmp = 2*i
    if tmp>=n: return None
    else: return tmp
    
def right(i, n):
    tmp = 2*i+1
    if tmp>=n: return None
    else: return tmp

def maxheapify(A, i):
    n = len(A)
    f = [0,0,0]
    f[0] = A[i]

    l=left(i, n)
    if l == None:
        f[1]=None
    else:
        f[1]=A[l]
    
    r=right(i,n)
    if r == None:
        f[2]=None
    else:
        f[2]=A[r]
        
    tmp = f.index(max(f))
    if tmp == 1:
        tmp=A[i]
        A[i]=A[l]
        A[l]=tmp
        maxheapify(A, l)
    elif tmp == 2:
        tmp=A[i]
        A[i]=A[r]
        A[r]=tmp
        maxheapify(A, r)

def buildmaxheap(A):
    for i in range(1,len(A))[::-1]:
        maxheapify(A,i)
        
n = int(input())
x = map(int, [0] + raw_input().split()) 
buildmaxheap(x)
print " "+" ".join(map(str, x[1:]))

Solution (Python):


from __future__ import division, print_function
from sys import stdin


def max_heapify(a, i, heap_size):
    L = 2*i
    R = 2*i + 1
    if L <= heap_size and a[L] > a[i]:
        largest = L
    else:
        largest = i
    if R <= heap_size and a[R] > a[largest]:
        largest = R
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest, heap_size)


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


heap_size = int(stdin.readline())
assert heap_size <= 500000
data = [0]
data.extend(int(s) for s in stdin.readline().split())
build_max_heap(data, heap_size)
print('', *data[1:])

Solution (Python):
import heapq
N = input()
H = [-x for x in map(int, input().split())]

heapq.heapify(H)
print("", *[-x for x in H])

Solution (Python):
def heapify(A, i):
    right_i = (i+1)*2-1
    left_i = (i+1)*2
    if right_i  > len(A)-1:
        return
    if left_i > len(A)-1:
        if A[right_i] > A[i] :
            A[right_i], A[i] = A[i], A[right_i ]
        return
    if A[i] < A[right_i] and A[left_i] < A[right_i ]:
        A[right_i ], A[i] = A[i], A[right_i ]     
        heapify(A, right_i )
    if A[i] < A[left_i] and A[right_i] < A[left_i]:
        A[left_i ], A[i] = A[i], A[left_i ]     
        heapify(A, left_i)

def build_heap(A):
    for i in reversed(range(len(A)//2)):
        heapify(A, i)

input()    
input_list = list(map(int, input().split()))
build_heap(input_list)

output = ""
for i in input_list:
    output += " " + str(i)
print(output)

Solution (Python):


def max_heapify(A, i):
    left = 2 * i + 1
    right = 2 * i + 2
    if left < len(A) and A[left] > A[i]:
        largest = left
    else:
        largest = i
    if right < len(A) and A[right] > A[largest]:
        largest = right

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


def main():
    h = int(input())
    A = [int(i) for i in input().split()]
    for i in range(0, h // 2)[::-1]:
        max_heapify(A, i)

    print(" " + " ".join([str(i) for i in A]))


if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heapify, heappop, heappush, heappushpop

N = int(input())
H = [-x for x in map(int,input().split())]

heapify(H)
print('', *[-x for x in H])

Solution (Python):

def maxHeapify(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(largest)

def buildMaxHeap(a):
    i = H//2 
    while i>=1:
        maxHeapify(i)
        i -= 1
    
    

H = int(input())
a = list(map(int,input().split()))
a.insert(0,0)
buildMaxHeap(a)
del a[0]
print(' ',end = "")
print(*a)

Solution (Python):
import sys
input = sys.stdin.readline

def parent(i):
    return i//2

def left(i):
    return 2*i

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

def maxHeapify(A, i):
    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, H):
    for i in range(H//2, 0, -1):
        maxHeapify(A, i)

H = int(input())
A = [None] + list(map(int, input().split()))

buildMaxHeap(A, H)

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

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')

parent = lambda i: math.floor(i / 2)
left = lambda i: 2 * i
right = lambda i: 2 * i + 1


def max_heapify(A, H, i):
    l = left(i) + 1
    r = right(i) + 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, H, largest)


def build_max_heap(A, H):
    for i in reversed(range(H // 2)):
        max_heapify(A, H, i)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H = ii()
    heap = il()
    build_max_heap(heap, H)
    print('', *heap)


if __name__ == '__main__':
    main()

Solution (Python):
class CompleteBinaryTree:
    def __init__(self, nodes):
        self.size = len(nodes)
        self.nodes = [None] + nodes
        
    
    def print_nodes(self):
        for i in range(1,self.size + 1):
            if i == 1:
                print('node {0}: key = {1}, left key = {2}, right key = {3}, '.format(i, self.nodes[i], self.nodes[2*i], self.nodes[2*i+1]))
            elif 2*i < self.size:
                print('node {0}: key = {1}, parent key = {2}, left key = {3}, right key = {4}, '.format(i, self.nodes[i], self.nodes[i//2], self.nodes[2*i], self.nodes[2*i+1]))
            elif 2*i == self.size:             
                print('node {0}: key = {1}, parent key = {2}, left key = {3}, '.format(i, self.nodes[i], self.nodes[i//2], self.nodes[2*i]))
            else:
                print('node {0}: key = {1}, parent key = {2}, '.format(i, self.nodes[i], self.nodes[i//2]))


    def _find_left(self, i):
        if 2*i <= self.size:
            return self.nodes[2*i]
        else:
            return -9999999999


    def _find_right(self, i):
        if 2*i+1 <= self.size:
            return self.nodes[2*i+1]
        else:
            return -9999999999


    def maxHeapify(self, i):
        n, l, r = self.nodes[i], self._find_left(i), self._find_right(i)
        if max(n, l, r) == l:
            self.nodes[i], self.nodes[2*i] = self.nodes[2*i], self.nodes[i]
            self.maxHeapify(2*i)
        elif max(n, l, r) == r:
            self.nodes[i], self.nodes[2*i+1] = self.nodes[2*i+1], self.nodes[i]
            self.maxHeapify(2*i+1)
            
    
    def buildMaxHeap(self):
        for i in range(self.size//2,0,-1):
            self.maxHeapify(i)


if __name__ == '__main__':
    n = int(input())
    nodes = list(map(int, input().rstrip().split()))
    cbt = CompleteBinaryTree(nodes)
    cbt.buildMaxHeap()
    print(' ' + ' '.join(map(str,cbt.nodes[1:])))

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

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

def maxHeapify(A, i):
    c = i
    l = 2*(i+1)-1 if 2*(i+1)<=H  else H+1
    r = 2*(i+1)+1-1 if 2*(i+1)+1<=H else H+1 

    
    if (l<=H) and (A[l]>A[c]):
        largest = l
    else:
        largest = c
    if (r<=H) and (A[r]>A[largest]):
        largest = r
        
    if largest!=c:
        A[c],A[largest] = A[largest],A[c]
        if 2*(largest+1)<=H:
            maxHeapify(A, largest)
    return A

def buildMaxHeap(A):
    for i in range(H//2-1, -1, -1):
        A = maxHeapify(A,i)
        
buildMaxHeap(A)
print(' '+' '.join([str(a) for a in A]))

Solution (Python):
from heapq import *
n = int(input())
H = [-x for x in map(int,input().split())]
heapify(H)
print(""," ".join([str(-x) for x in H]))

Solution (Python):
H = int(input())
A = [0] + list(map(int, input().split()))

def maxHeapify(A, i):
    l = i*2
    r = i*2 + 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[largest], A[i] = A[i], A[largest]
        maxHeapify(A, largest)

for x in range(H//2, 0, -1):
    maxHeapify(A, x)

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

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

def maximum_heap(nums,i):
    left_index=2*(i+1)-1
    right_index=2*(i+1)
    if left_index<n and nums[left_index]>nums[i]:
        largest=left_index
    else:
        largest=i
    if right_index<n and nums[right_index]>nums[largest]:
        largest=right_index
    
    if largest!=i:
        nums[largest],nums[i]=nums[i],nums[largest]
        maximum_heap(nums,largest)

for i in range(int(n/2)-1,-1,-1):
    maximum_heap(nums,i)

print(" ",end="")
for i in range(n):
    if i!=n-1:
        print(nums[i],end=" ")
    else:
        print(nums[i])

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

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

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

n = int(input())
h = list(map(int, input().split()))
buildMaxHeap()
print('', *h)

Solution (Python):
from heapq import heapify, heappop, heappush, heappushpop
N = input()
H = [-x for x in map(int, input().split())]

heapify(H)
print('', *[-x for x in H])

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H = I()
    A = [0]
    tmp = LI()
    for i in tmp:
        A.append(i)

    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)

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

    buildMaxHeap(A)

    ans = ''
    for i in range(1, H+1):
        ans += ' ' + str(A[i])
    print(ans)

if __name__ == '__main__':
    resolve()

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

def parent(i):
    i += 1
    return int(i/2) -1

def left(i):
    i += 1
    return 2*i -1

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

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

    
    return A
        
def buildMaxHeap(A):
    for i in range(int(len(A)/2)-1, -1, -1):
        A = maxHeapify(A, i)
    return A

A = buildMaxHeap(A)

print(" {}".format(" ".join([str(i) for i in A])))

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

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

n = int(input())
A = [''] + list(map(int, input().split()))
buildMaxHeap(A)

print(*A)

Solution (Python):
def readinput():
    h=int(input())
    a=list(map(int,input().split()))
    a.insert(0,-1)
    return h,a

def maxHeapify(a,i):
    h=len(a)-1
    l=i*2
    r=i*2+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)

def buildHeap(a):
    h=len(a)-1
    for i in range(h//2, 0, -1):
        maxHeapify(a,i)


def main(h,a):
    buildHeap(a)
    return a

if __name__=='__main__':
    h,a=readinput()
    ans=main(h,a)
    print(' ',end=''); print(' '.join(map(str,a[1:])))

Solution (Python):

def MaxHeap(A, i):
    
    l = i * 2
    r = i * 2 + 1

    largest = i

    if l < len(A):
        if A[i] < A[l]:
            largest = l
            

    
    if r < len(A):
        if A[largest] < A[r]:
            largest = r
            
    
    if largest != i: 
        tmp = A[i]
        
        A[i] = A[largest]
        A[largest] = tmp

        MaxHeap(A, largest)

def BuildHeap(A):
    length = len(A)//2

    for k in range(length, 0, -1):
        
        MaxHeap(A, k)
   

    return A

n = input()

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

A = BuildHeap(A)

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

print("")

"""
10
4 1 3 2 16 9 10 14 8 7 
"""

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

    if l < len(A) and A[l] > A[i]:
        largest = l
    else:
        largest = i
    
    if r < len(A) and A[r] > A[largest]:
        largest = r

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

if __name__ == "__main__":
    n = int(input())
    heap = list(map(int,input().split()))
    heap.insert(0,0)

    for i in range(int(len(heap)/2),0,-1):
        maxheapify(heap,i)

    for n in range(1,len(heap)):
        print(' {}'.format(heap[n]),end='')
    print()

Solution (Python):
def left(i:int):
    return i * 2

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

def maxHeapify(A:list, i:int):
    l = left(i)
    r = right(i)
    global H
    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:list):
    global H
    for i in range(int(H/2), 0, -1):
        maxHeapify(A, i)

H = int(input())
A = [None]
A.extend(list(map(int,input().split())))
buildMaxHeap(A)
print(" ", end="")
print(*A[1:])

Solution (Python):
H = int(input().rstrip())
Ai = [int(i) for i in input().rstrip().split()]

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

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

buildMaxHeap(Ai)
for a in Ai:
    print(" "+str(a),end="")
print()

Solution (Python):
n = int(input())
a = [0] + list(map(int,input().split()))
def heapSort(a, i):
    global n
    l = 2 * i
    r = 2 * i + 1
    largest = l if l <= n and a[l] > a[i] else i
    if r <= n and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[largest], a[i] = a[i], a[largest]
        heapSort(a, largest)

for i in range(int( n / 2 ), 0, -1):
    heapSort(a, i)
print(" "+" ".join(map(str,a[1:])))

Solution (Python):
from sys import stdin
N=int(input())
n=list(map(int,(stdin.readline().strip().split())))
n.insert(0,None)
def maxheap(A,i):
    right=i*2+1
    left=i*2
    if left<=N and A[left]>A[i]:
        max_i=left
    else:
        max_i=i
    if right<=N and A[right] >A[max_i]:
        max_i=right
    if max_i!=i:
        A[i],A[max_i]=A[max_i],A[i]
        maxheap(A,max_i)
def build(A):
    for i in range(N//2,0,-1):
        maxheap(A,i)
build(n)
for i in range(1,N+1):
    print("",n[i],end="")
print()

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

class HeapTree:
    def __init__(self,A):
        self.heap = [-1] + A
        self.l = len(self.heap)-1
        self.buildMaxHeap()


    def maxHeapify(self,i):
        left_child = self.left_child(i)
        right_child = self.right_child(i)
        larger = i
        if left_child and self.heap[left_child] > self.heap[i]:
            larger = left_child
        if right_child and self.heap[right_child] > self.heap[larger]:
            larger = right_child
        
        if larger != i:
            tmp = self.heap[i]
            self.heap[i] = self.heap[larger]
            self.heap[larger] = tmp
            self.maxHeapify(larger)

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

    def left_child(self,i):
        if 2*i <= self.l:
            return 2*i
        else:
            return False
            
    def right_child(self,i):
        if 2*i+1 <= self.l:
            return 2*i+1
        else:
            return False
    
    def buildMaxHeap(self):
        max_ind_parent = self.parent(self.l)
        for i in range(max_ind_parent,0,-1):
            self.maxHeapify(i)

heap_tree = HeapTree(A)
print(" ",end="")
print(*heap_tree.heap[1:])

Solution (Python):
h = int(input())
A = list(map(int, input().split()))
A.insert(0, 0) 

def maxHeapify(i):
    left = 2 * i
    right = 2 * i + 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(largest)


for i in range(h // 2, 0, -1):
    maxHeapify(i)

print(' ' + ' '.join([str(i) for i in A[1:]]))

Solution (Python):
N = int(input())
H = [int(h) for h in input().split()]

def max_heapfiy(i):
    left = 2 * i
    right = 2 * i + 1
    if left <= N and H[i - 1] < H[left - 1]:
        largest = left
    else:
        largest = i
    if right <= N and H[largest - 1] < H[right - 1]:
        largest = right
    if largest != i:
        H[i - 1], H[largest - 1] = H[largest - 1], H[i - 1]
        max_heapfiy(largest)

for i in reversed(range(1, N // 2 + 1)):
    max_heapfiy(i)

print('', *H)

Solution (Python):
def left_child(i):
    if 2*i >= len(L):
        return 0
    else :
        return int(2*i)

def right_child(i):
    if 2*i+1 >= len(L):
        return 0
    else :
        return int(2*i + 1)
        
N=int(input())
L=list(map(int,input().split()))
L = [-3000000000]+L
    
H = int(N/2)
for h in range(H ,0,-1):
    while True:

        l_c = left_child(h)
        r_c = right_child(h)

        L_h=L[h]
        L_l_c=L[l_c]
        L_r_c=L[r_c]

        if L[l_c] > L[r_c] and L[l_c] > L[h]:
            L[h] = L_l_c
            L[l_c] = L_h
            h = l_c

        elif L[l_c] < L[r_c] and L[r_c] > L[h]:
            L[h] = L_r_c
            L[r_c] = L_h
            h = r_c

        else:
            break
L=L[1:]
L=['']+L
print(' '.join(map(str,L)))

Solution (Python):
def MaxHeapify(a,i):
    l = i*2
    r = i*2+1
    j = i
    if l<len(a) and a[l]>a[j]:j = l
    if r<len(a) and a[r]>a[j]:j = r
    if j!=i:
        a[i],a[j] = a[j],a[i]
        MaxHeapify(a,j)


def init(a):
    for i in reversed(range(1,len(a)//2+1)):
        MaxHeapify(a,i)

def main():
    n = int(input())+1
    a = [-1]+list(map(int,input().split()))
    init(a)
    for i in range(1,n):print (' %d'%a[i],end='')
    print ()


if __name__ == '__main__':
    main()

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

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

for i in range(1,H//2+1)[::-1]: maxHeapify(i)
for i in range(1,H+1): print(" {}".format(A[i]),end="")
print("")

Solution (Python):



def left(i):
    return 2 * i


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


def maxHeapify(A, i):
    l = left(i)
    r = right(i)
    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:
        tmp = A[i]
        A[i] = A[largest]
        A[largest] = tmp
        maxHeapify(A, largest)

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

H = int(input())
A = [-1] + [int(i) for i in input().split()]
buildMaxHeap(A)
for i in range(1, H+1):
    if i == H+1:
        print(A[i])
    else:
        print(" ", A[i], sep="", end="")
print()

Solution (Python):


H = int(input())
*A, = map(int, input().split())
A = [0] + A


def left(i):
    return i*2


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


def max_heapify(i):
    l = left(i)
    r = right(i)

    M = l if l <= H and A[l] > A[i] else i
    M = r if r <= H and A[r] > A[M] else M

    if M != i:
        A[i], A[M] = A[M], A[i]
        max_heapify(M)


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


build_max_heap()
print('', *A[1:])

Solution (Python):
def resolve():
    '''
    code here
    '''
    import heapq
    N = int(input())
    input_list = [-1 * int(item) for item in input().split()]

    heapq.heapify(input_list)

    input_list = [-1 * item for item in input_list]
    print('', *input_list)


if __name__ == "__main__":
    resolve()