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):
import sys
sys.setrecursionlimit(15000)
n = int(input())
A = [0]+list(map(int,input().split()))

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

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

buildMaxHeap(A)
print(" ",end="")
print(" ".join(map(str,A[1:])))

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

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

    if r <= len(A) - 1 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 reversed( range(1, int(  ( len(A) - 1 ) / 2.0 ) + 1 ) ):
        maxheapify(A, i)

def Main():
    n = int(input())
    A = [-1] + [ int(a) for a in input().split()]
    buildmaxheap(A)
    res = [" " + str(a) for a in A]
    print("".join(res[1:]))
    
Main()

Solution (Python):
class MaxHeap:

    @classmethod
    def heapify(cls, array):
        size = len(array)
        for i in reversed(range(size // 2)):
            cls.siftdown(array, i, size)

    @classmethod
    def push(cls, heap, x):
        heap.append(x)
        cls.siftup(heap, len(heap) - 1)

    @classmethod
    def pop(cls, heap):
        if heap:
            heap[0], heap[-1] = heap[-1], heap[0]
            res = heap.pop()
            cls.siftdown(heap, 0, len(heap) - 1)
            return res
        else:
            return None

    @staticmethod
    def peek(heap):
        return heap[0]

    @staticmethod
    def siftup(heap, i):
        parent = (i - 1) // 2
        while i > 0 and heap[i] >= heap[parent]:
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
            parent = (i - 1) // 2

    @staticmethod
    def siftdown(heap, i, size):
        while True:
            left = 2 * i + 1
            right = 2 * i + 2
            largest = left
            if right < size and heap[right] > heap[left]:
                largest = right

            if left >= size or heap[i] > heap[largest]:
                break

            heap[i], heap[largest] = heap[largest], heap[i]
            i = largest


if __name__ == '__main__':
    input()
    array = list(map(int, input().split()))
    MaxHeap.heapify(array)
    print(' ' + ' '.join(map(str, array)))

Solution (Python):


def max_heapify(A, idx):
    left = (idx+1)*2-1
    right = (idx+1)*2
    
    largest = idx
    if left < len(A) and A[largest] < A[left]:
        largest = left
    if right < len(A) and A[largest] < A[right]:
        largest = right
    if largest != idx:
        A[idx], A[largest] = A[largest], A[idx]
        max_heapify(A, largest)

def build_max_heap(A):
    
    for i in range(len(A)//2, -1, -1):
        max_heapify(A, i)
        
    
n = int(input())

a = [int(i) for i in input().split()]

build_max_heap(a)

print('', *a)

Solution (Python):
def left(i):return  2 * i + 1
def right(i):return  2 * i + 2
def max_heapify(a, i):
    l = left(i)
    r = right(i)
    largest = l if  l < len(a) and a[l] > a[i] else i
    largest = r if  r < len(a) and a[r] > a[largest] else largest
    
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest)
        
def build_max_heap(a):
    for i in range(len(a) // 2, -1, -1):
        max_heapify(a, i)
n = int(input())
heap = list(map(int, input().split()))
build_max_heap(heap)
print('', *heap)

Solution (Python):
import sys

def maxHeapify(heap, i):
    h = len(heap) - 1 
    l = 2 * i
    r = 2 * i + 1
    if l <= h and heap[i] < heap[l]:
        largest = l
    else:
        largest = i
    if r <= h and heap[largest] < heap[r]:
        largest = r

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

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



size = int(input())
heap = [i for i in map(int, input().split())]
heap = [0] + heap 

buildMaxHeap(heap)
for i in range(1, len(heap)):
    print(' ', end='')
    print(heap[i], end='')
    if i == len(heap)-1:
        print('')

Solution (Python):
import copy

n = int(input())
nodes = list(map(int, input().split()))
heap = copy.deepcopy(nodes)
heap.insert(0, None)

MIN_INF = -10 ** 10
heap.append(MIN_INF)


def max_heapify(i):
  l = 2 * i
  r = 2 * i + 1

  if l <= n and heap[l] > heap[r] and heap[l] > heap[i]:
    heap[l], heap[i] = heap[i], heap[l]
    max_heapify(l)
  elif r <= n and heap[l] < heap[r] and heap[r] > heap[i]:
    heap[r], heap[i] = heap[i], heap[r]
    max_heapify(r)

  

i = n // 2
while i != 0:
  max_heapify(i)
  i -= 1

print(" " + " ".join([str(i) for i in heap[1:-1]]))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
def heapfy(A, i, n):
    x = A[i]
    l,r = None, None
    if (i+1)*2-1<n:
        l = A[(i+1)*2-1]    
    if (i+1)*2<n:
        r = A[(i+1)*2]
    
    largest = i
    if l is not None and r is not None:
        if l>r:
            if l>x:
                largest = (i+1)*2-1
        else:
            if r>x:
                largest = (i+1)*2
    elif l is None and r is None:
        pass
    elif l is None:
        if r>x:
            largest = (i+1)*2
    elif r is None:
        if l>x:
            largest = (i+1)*2-1
    
    
    if largest!=i:
        A[i], A[largest] = A[largest], A[i]
        heapfy(A, largest, n)
        
def buildMaxHeap(A, n):
    for i in range(n//2-1, -1, -1):
        heapfy(A, i, n)
        

buildMaxHeap(a, n)

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

Solution (Python):
INF = 2*10**9+1

H = int(input())
Heap = [-INF]
Heap += list(map(int,input().split()))

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

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

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

buildMaxHeap(Heap)
print(""," ".join(map(str,Heap[1:H+1])))

Solution (Python):
def max_heapify(A, i):
    left_id = 2 * i
    right_id = left_id + 1

    largest_id = i
    if left_id <= len(A) and A[left_id - 1] > A[largest_id - 1]:
        largest_id = left_id
    if right_id <= len(A) and A[right_id - 1] > A[largest_id - 1]:
        largest_id = right_id
    
    if i != largest_id:
        A[i - 1], A[largest_id - 1] = A[largest_id - 1], A[i - 1]
        max_heapify(A, largest_id)

def show(A):
    for i in A:
        print('', i, end = '')
    print()

heap_size = int(input())
A = list(map(int, input().split()))
for i in range(heap_size // 2, 0, -1):
    max_heapify(A, i)
show(A)

Solution (Python):
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    H = int(input())

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

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

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

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

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

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

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

H = int(input())

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

buildMaxHeap(A)

print(" " + " ".join(list(map(str, A))))

Solution (Python):
def max_heapify(i):
    l = i*2
    r = i*2+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]
        max_heapify(largest)

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

if __name__ == "__main__":
    H = int(input())
    A = list(map(int, input().split()))
    build_max_heap()
    print(" ", end="")
    print(*A)

Solution (Python):

N = int(input())
heap = list(map(int, input().split()))
heap = [0]+ heap

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

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

build_maxheap(heap)
print('', *heap[1:])

Solution (Python):
H = int(input())
def max_heapify(A, i):
    left = i*2
    right = i*2+1
    largest = i
    if left <= H and A[left-1] > A[i-1]:
        largest = left
    if right <= H and A[right-1] > A[largest-1]:
        largest = right
    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):
    for i in range(1, H//2+1)[::-1]:
        max_heapify(A, i)
A = list(map(int, input().split(' ')))
build_max_heap(A)
str_A = " ".join(map(str, A))
print(" {}".format(str_A))

Solution (Python):
import math

def maxHeapify(s):
	
	l = s * 2
	r = l + 1

	if l <= main[0] and main[l] > main[s]:
			
			largest = l
	else:
		largest = s
	if r <= main[0] and main[r] > main[largest]:
		
		largest = r

	if largest != s:
		

		swa = main[s]
		main[s] = main[largest]
		main[largest] = swa
		maxHeapify(largest)


n = input()

main = list(map(int, input().split()))
main.insert(0,int(n))



del n

for i in range(math.floor(main[0]/2),0,-1):
	
	maxHeapify(int(i))

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

print()

Solution (Python):
"""
ALDS1_9_B
最大ヒープを実装する
"""
import copy
import math

def get_parent(index):
    parent_index = math.floor((index-1)/2)
    return parent_index
    
def get_left(index):
    left_index = 2*index+1
    return left_index

def get_right(index):
    right_index = 2*index+2
    return right_index

def maxHeapify(A, i): 
    l = get_left(i)
    r = get_right(i)
    if A[l] and A[r]: 
        if l < n and A[l] > A[i]: 
            largest = l
        else:
            largest = i
            
        if r < n and A[largest] < A[r]:
            largest = r
        
        if largest == i: 
            pass
        else:
            A[largest], A[i] = A[i], A[largest]
            maxHeapify(A, largest)
    
    elif not A[r]: 
        if l < n and A[l] > A[i]:
            A[l], A[i] = A[i], A[l]
            maxHeapify(A, l)
    
    else:
        pass



n = int(input())
heap_list = list(map(int, input().split()))+[None]*(n+1)

roop = math.floor(n/2)-1
for i in range(roop, -1, -1):
    maxHeapify(heap_list, i)


for i in range(n):
    k = heap_list[i]
    print(' '+str(k), end='')
print()

Solution (Python):
def max_heapify(A, i):
    left_id = 2 * i
    right_id = left_id + 1

    largest_id = i
    if left_id <= len(A) and A[left_id - 1] > A[largest_id - 1]:
        largest_id = left_id
    if right_id <= len(A) and A[right_id - 1] > A[largest_id - 1]:
        largest_id = right_id
    
    if i != largest_id:
        A[i - 1], A[largest_id - 1] = A[largest_id - 1], A[i - 1]
        max_heapify(A, largest_id)


import sys

heap_size = int(input())
A = list(map(int, sys.stdin.readline().split()))
for i in range(heap_size // 2, 0, -1):
    max_heapify(A, i)
print('', *A)

Solution (Python):
from heapq import heapify, heappop

n =int(input())
b = [-x for x in map(int, input().split())]

heapify(b)
print("", *[-x for x in b])

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

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


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


n=int(input())+1
A=[0]+list(map(int,input().split()))
buildMaxHeap(A)
print(" ",end="")
print(*A[1:])

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

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

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

def maxHeapify(A, i):
	l = i*2
	r = i*2+1
	if l <= n and A[l-1] > A[i-1]:
		largest = l
	else: 
		largest = i
	if r <= n 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)
for i in range(n//2,0,-1):
	maxHeapify(a,i)
print(" ",end="")
print(*a)

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


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


H = int(input())
A = list(map(int, input().split()))
A.insert(0, None)
buildMaxHeap(A)
print(' ' + ' '.join(map(str, A[1:])))

Solution (Python):

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

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

n=int(input())
heap = list(map(int,input().split()))
heap.insert(0, None)

buildMaxHeap(heap)
print(" ", end = "")
for i in range(n - 1):
    print(heap[i + 1 ], end = " ")
print(heap[n], end = "")
print("")

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

def build_maxheap():
    for i in range((H+1)//2, 0, -1):
        max_heapify(i)
    
H = int(input())
A = [None]
A.extend(list(map(int, input().split())))

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

Solution (Python):
class Heap():
    def __init__(self, numlist):
        self.datas = numlist
        self.size = len(numlist)
        self.buildMaxHeap()

    def maxHeapify(self, i):
        if i > self.size:
            return
        
        l = i * 2 + 1
        r = i * 2 + 2
        max_index = i

        if l < self.size and self.datas[l] > self.datas[max_index]:
            max_index = l
        if r < self.size and self.datas[r] > self.datas[max_index]:
            max_index = r
        
        if max_index != i:
            self.datas[max_index], self.datas[i] = self.datas[i], self.datas[max_index]
            self.maxHeapify(max_index)
    
    def buildMaxHeap(self):
        index = self.size // 2
        while index >= 0:
            self.maxHeapify(index)
            index -= 1

    def show(self):
        print(' ' + str(self.datas).replace(',', '').replace('[', '').replace(']', ''))


if __name__ == '__main__':
    n = input()
    numlist = [int(num) for num in input().split(' ')]
    maxheap = Heap(numlist)
    maxheap.show()

Solution (Python):

def parent(i):
    return i // 2


def left(i):
    return 2 * i


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


def max_heapify(i):
    global A

    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]
        max_heapify(largest)  


H = int(input())
A = [None] * (H + 1)

_ = list(map(int, input().split()))
A[1:] = _

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

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

Solution (Python):
def maxHeapify(T,i):
    l=2*i+1
    r=2*(i+1)
    H=len(T)
    left=l<H and T[i]<T[l]
    right=r<H and T[i]<T[r]
    if left and right:
        if T[r]<T[l]:
            right=0
        else:
            left=0
    if left:
        T[i],T[l]=T[l],T[i]
        maxHeapify(T,l)
    elif right:
        T[i],T[r]=T[r],T[i]
        maxHeapify(T,r)
        


H=int(input())
Nodes=[int(i) for i in input().split()]
for i in range(H-1,-1,-1):
    maxHeapify(Nodes,i)
print('',*Nodes)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
def maxHeapify(A, i):
    if 2*i+1 < len(A):
        left = A[2*i+1]
        if 2*i+2 < len(A):
            right = A[2*i+2]
            if right < left and left > A[i]:
                A[i], A[2*i+1] = A[2*i+1], A[i]
                maxHeapify(A, 2*i+1)
            elif left < right and right > A[i]:
                A[i], A[2*i+2] = A[2*i+2], A[i]
                maxHeapify(A, 2*i+2)
        elif left > A[i]:
            A[i], A[2*i+1] = A[2*i+1], A[i]
            maxHeapify(A, 2*i+1)
i = (len(A)-1-1)//2
while i >= 0:
    maxHeapify(A, i)
    i-=1
ans = ''
for i in range(len(A)):
    ans+=' '+str(A[i])
print(ans)

Solution (Python):
def maxHeapify(A, i):
    global H
    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):
    global H
    for i in reversed(range(int((H + 1) / 2))):
        maxHeapify(A, i)

H = int(input())
A = list(map(int, input().split(" ")))
buildMaxHeap(A)
print(" ", end = '')
print(' '.join(map(str, A)))

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):
def heapify(V, H, i):
  l, r = i*2+1, i*2+2
  iv = V[i]
  lv = V[l] if l < H else -1e10
  rv = V[r] if r < H else -1e10
  if lv > iv and lv >= rv:
    V[i] = lv
    V[l] = iv
    heapify(V, H, l)
  elif rv > iv:
    V[i] = rv
    V[r] = iv
    heapify(V, H, r)

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

for i in range(H-1, -1, -1):
  heapify(V, H, i)
print(''.join([' '+str(v) for v in V]))

Solution (Python):
from typing import List

def parent(i: int) -> int:
	return i // 2

def left(i: int) -> int:
	return 2 * i

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


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


if __name__ == "__main__":
	H = int(input())
	A = [None] + list(map(int, input().split()))
	buildMaxHeap(A)
	for i in range(1, H + 1):
		print(f" {A[i]}", end="")
	print()

Solution (Python):
MAX = 500000
H = None

def parent(i):
    return i//2


def left(i):
    return 2*i


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


def max_heapify(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[largest], A[i] = A[i], A[largest]
        max_heapify(A, largest)


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


def main():
    global H
    H = int(input())
    A = [0] * (MAX+1)

    v_s = input().split(' ')

    for i in range(H):
        A[i+1] = int(v_s[i])

    build_max_heap(A)

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


if __name__ == '__main__':
    main()

Solution (Python):

import sys

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

    largest = i

    if l <= H:
        if A[l] > A[largest]:
            largest = l

    if r <= H:
        if A[r] > A[largest]:
            largest = r

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


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

H = int(input())

A = list(map(int, sys.stdin.readline().strip().split()))
A.insert(0, None)
buildmaxheap(A)
A.remove(None)
print('', ' '.join(map(str, A)))

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

def maxHeapify(A: list, i: int):
    H = len(A) - 1
    l = 2 * i
    r = l + 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)
    return

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

def main():
    H = int(input())
    A = [0] + list(map(int, input().split()))
    buildMaxHeap(A)
    for i in range(1, H+1):
        print(' {}'.format(A[i]), end='')
    print()

if __name__ == '__main__': main()

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

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

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

def max_heapify(h, i):
  l = left(i)
  r = right(i)
  largest = i
  if l < H and h[l] > h[largest]:
    largest = l
  if r < H and h[r] > h[largest]:
    largest = r

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

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

build_max_heap(A)
print(" " + " ".join(list(map(str, A))))

Solution (Python):
def maxHeapiify(A, i, n):
    l = 2*i+1
    r = 2*i+2
    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]
        maxHeapiify(A, largest, n)


def buildMaxHeap(A, n):
    for i in range(n//2, -1, -1):
        maxHeapiify(A, i, n)


def main():
    N = int(input())
    H = list(map(int, input().split()))
    buildMaxHeap(H, N)
    print(" ", end="")
    print(*H)


if __name__ == '__main__':
    main()

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


def build_max_heap(a):
    heap_size = len(a)
    for i in reversed(range(0, heap_size // 2)):
        max_heapify(a, i)


def main():
    _ = int(input())
    a = list(map(int, input().split()))
    build_max_heap(a)
    for it in a:
        print(' {}'.format(it), end='')
    print()


if __name__ == '__main__':
    main()

Solution (Python):
from typing import List


def max_heapify(heap: List[int], idx: int) -> None:
    left_idx = (2 * (idx + 1)) - 1
    right_idx = (2 * (idx + 1))

    if len(heap) - 1 >= left_idx and heap[left_idx] > heap[idx]:
        largest_idx = left_idx
    else:
        largest_idx = idx

    if len(heap) - 1 >= right_idx and heap[right_idx] > heap[largest_idx]:
        largest_idx = right_idx

    if largest_idx != idx:
        heap[largest_idx], heap[idx] = heap[idx], heap[largest_idx]
        max_heapify(heap, largest_idx)


def build_max_heap(heap: List[int]) -> None:
    for idx in range(len(heap) // 2 - 1, -1, -1):
        max_heapify(heap, idx)


if __name__ == "__main__":
    node_num = int(input())
    heap = list(map(lambda x: int(x), input().split()))

    build_max_heap(heap)

    print(" " + " ".join([str(elem) for elem in heap]))

Solution (Python):
def parent(i):
    return(i // 2)

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

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

def maxHeapify(i):
    l = left(i)
    r = right(i)
    largest = 0
    
    if l <= H and A_list[l] > A_list[i]:
        largest = l
    else:
        largest = i
        
    if r <= H and A_list[r] > A_list[largest]:
        largest = r
    
    if largest != i:
        tmp_val = A_list[largest]
        A_list[largest] = A_list[i]
        A_list[i] = tmp_val
        maxHeapify(largest)

H = int(input())
A_list = list(map(int, input().split()))
A_list.insert(0, 0)
for i in range(H // 2, 0, -1):
    
    
    maxHeapify(i)
for i in range(1, H+1):
    print(" ", A_list[i], sep="", end="")
print("")

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

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


n = int(input())
arr = list(map(int, input().split()))
build_max_heap(arr)
print(" ", end="")
print(*arr)

Solution (Python):
KEY_MIN = -2000000001


H = int(input())

A = [KEY_MIN] * (H + 1)

for cnt, key in enumerate(map(int, input().split())):
    A[cnt + 1] = key

index_min = 1
index_max = len(A) - 1

def index_exsist(i):
    if index_min <= i <= index_max:
        return i
    else:
        return 0

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

    largest = i
    if A[l] > A[largest]:
        largest = l
    if A[r] > A[largest]:
        largest = r

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

def build_maxheap(A):
    for i in range(1, (H // 2) + 1)[::-1]:
        max_heapify(A, i)


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

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

def buildmaxheap(h,a):
    for i in range((h-1)//2,-1,-1):
        maxheapify(h,a,i)
    return a

h=int(input())
a=list(map(int,input().split()))
ans=buildmaxheap(h,a)
print("",end=" ")
for i in range(h-1):
    print(ans[i],end=" ")
print(ans[h-1])

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

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

for v in A:
    print('', v, end='')
print('')

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

def left(i):
    return i*2

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

def maxHeapify(A, i):
    H = len(A)
    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]
        A = maxHeapify(A, largest)
    return A

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

A = buildMaxHeap(B)
print("", *A)

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

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

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

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

if __name__ == "__main__":
    H = int(input())
    A = [-1] + list(map(int, input().split()))
    buildMaxHeap(H)
    print(' ' + ' '.join(map(str, A[1:])))