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
input = sys.stdin.readline

H = int(input())
h = [int(ele) for ele in input().split()]
h = [0] + h


def main():
    max_heap = HeapHelper.build_max_heap(h)
    ans = ''
    for val in max_heap[1:]:
        ans += ' ' + str(val)

    print(ans)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
        if i != n // i:
            divisors.append(n//i)
    return divisors


class Node():

    def __init__(self):
        self.idx = None
        self.left = None
        self.right = None
        self.parent = None
        return

    def pre_order(self):
        global pre_order_str
        pre_order_str += str(self.idx) + " "
        if self.left:
            self.left.pre_order()

        if self.right:
            self.right.pre_order()

    def in_order(self):
        global in_order_str

        if self.left:
            self.left.in_order()

        in_order_str += str(self.idx) + " "

        if self.right:
            self.right.in_order()

    def post_order(self):
        global post_order_str
        if self.left:
            self.left.post_order()

        if self.right:
            self.right.post_order()

        post_order_str += str(self.idx) + " "


class HeapHelper():
    """HeapContrler.
    完全二分木を二分ヒープで表現した配列 A に対して、
    HeapHelper.parent(idx) とするとそのノードの親の添字を返す
    存在しない場合は Falseを返す

    Returns:
        [type] -- [description]
    """

    def __init__(self):
        return

    @staticmethod
    def parent(i):
        if i == 1:
            return False

        return int(i/2)

    @staticmethod
    def left(i):
        l_idx = 2*i
        if H < l_idx:
            return False

        return l_idx

    @staticmethod
    def right(i):
        r_idx = 2*i + 1
        if H < r_idx:
            return False

        return r_idx

    @staticmethod
    def build_max_heap(heap):
        for idx in range(len(heap)-1, 0, -1):
            HeapHelper.max_heap(heap, idx)

        return heap

    @staticmethod
    def max_heap(heap, i):
        """ 

        Arguments:
            heap {[type]} -- [description]
            i {[type]} -- [description]
        """
        l = HeapHelper.left(i)
        r = HeapHelper.right(i)
        largest = i
        
        if l != False and heap[l] > heap[i]:
            largest = l

        if r != False and heap[r] > heap[largest]:
            largest = r

        if largest != i:
            tmp = heap[largest]
            heap[largest] = heap[i]
            heap[i] = tmp
            HeapHelper.max_heap(heap, largest)


if __name__ == "__main__":
    main()

Solution (Python):
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 left(i):
    return i*2


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


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


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

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

Solution (Python):
n = int(input())
nums = list(map(int,input().split(" ")))
nodes = []

class Node():
    def __init__(self,value):
        self.value = value
        self.parent = None
        self.left = None
        self.right = None

    def defineParent(self,parent):
        self.parent = parent

    def defineLeft(self,left):
        self.left = left

    def defineRight(self,right):
        self.right = right

def heapify(nums,parentIndex,root):
    leftIndex = parentIndex*2+1
    rightIndex = parentIndex*2+2
    rightFlag = False
    leftFlag = False
    if leftIndex < len(nums):
        leftNode = Node(nums[leftIndex])
        root.left = leftNode
        leftNode.parent = root
        nodes[leftIndex] = leftNode
        leftFlag = True
    if rightIndex < len(nums):
        rightNode = Node(nums[rightIndex])
        root.right = rightNode
        rightNode.parent = root
        nodes[rightIndex] = rightNode
        rightFlag = True
    if leftFlag:
        heapify(nums,leftIndex,leftNode)
    if rightFlag:
        heapify(nums,rightIndex,rightNode)

def doIt(l):
    leftIndex = 2*l+1
    rightIndex = 2*l+2
    vsNodes = [nodes[l].value]
    nextIndex = []
    if leftIndex < len(nodes):
        nextIndex.append(leftIndex)
        vsNodes.append(nodes[leftIndex].value)
    if rightIndex < len(nodes):
        nextIndex.append(rightIndex)
        vsNodes.append(nodes[rightIndex].value)
    maximumValue = max(vsNodes)
    if maximumValue > nodes[l].value:
        if maximumValue == nodes[leftIndex].value:
            changeIndex = leftIndex
        elif maximumValue == nodes[rightIndex].value:
            changeIndex = rightIndex
        tmp = nodes[l]
        nodes[l] = nodes[changeIndex]
        nodes[changeIndex] = tmp
        doIt(changeIndex)

def maxHeapify(nodes):
    startIndex = len(nodes)//2
    for l in range(startIndex,-1,-1):
        doIt(l)


nodes = [None]*len(nums)
treeRoot = Node(nums[0])
nodes[0] = treeRoot
heapify(nums,0,treeRoot)



flag = True
while flag:
    flag = maxHeapify(nodes)

ans = ""
for i in nodes:
    ans += " " + str(i.value)

print(ans)

Solution (Python):
h = int(input())
n = [0]*(h+1)
n[1:] = [int(v) for v in input().split()]


def left(i):
    return i*2


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


def maxHeapify(a, i):
    l, r = left(i), right(i)
    mi = i
    if l <= h and a[l] > a[i]:
        mi = l
    if r <= h and a[r] > a[mi]:
        mi = r

    if i != mi:
        a[i], a[mi] = a[mi], a[i]
        maxHeapify(a, mi)


def buildMaxHeap(a):
    i = h//2
    while i > 0:
        maxHeapify(a, i)
        i -= 1


buildMaxHeap(n)
print(" "+" ".join([str(v) for v in n[1:]]))

Solution (Python):
H = int(input())
a = list(map(int, input().split()))
def maxHeapify(A, i):
    l = 2*i + 1
    r = 2*i + 2
    largest = i
    if l<H and A[largest] < A[l]:
        largest = l 
    if r<H and A[largest] < A[r]:
        largest = r
    if largest != i:
        A[i],A[largest] = A[largest],A[i]
        maxHeapify(A, largest)

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

buildHeap(a)

print(' '+' '.join(list(map(str, a))))

Solution (Python):
H = int(input())
A = [0]

s = input().split()
for si in s:
    A.append(int(si))


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[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)


build_max_heap(A)
print("", " ".join([str(i) for i in A[1:]]))

Solution (Python):

"""
Created on Wed Mar  6 22:11:30 2019

@author: Yamazaki Kenichi
"""

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

class MaxHeap(object):
    def __init__(self,size):
        self.table = [-1 for i in range(size+1)]
    
    def p(self,u):
        return u//2
    def left(self,u):
        return u*2
    def right(self,u):
        return u*2+1
    def swap(self,A,i,size):
        l = self.left(i)
        r = self.right(i)

        if l <= size and A[l] > A[i]:
            largest = l
        else:
            largest = i
        if r <= size and A[r] > A[largest]:
            largest = r
        if largest != i:
            A[i],A[largest] = A[largest],A[i]

            self.swap(A,largest,size)

mh = MaxHeap(H)
for i in range(H):
    mh.swap(A,H-i,H)
A = map(str,A)
print(' '.join(A))

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):
import sys
readline = sys.stdin.readline
write = sys.stdout.write

err = -2 * (10**9) + 1

class Node:
    def __init__(self, k, l, r, p):
        self.key = k
        self.left = l
        self.right = r
        self.parent = p

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

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

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

n = int(input())
keys = list(map(int, readline().split()))

Heap = [Node(err, None, None, None) for i in range(n+1)]
for i in range(1, n+1):
    Heap[i].key = keys[i-1]
    if 2*i  < n+1:
        Heap[i].left = Heap[2*i]
    if 2*i + 1 < n+1:
        Heap[i].right = Heap[2*i + 1]
    if i > 1:
        Heap[i].parent = Heap[int(i/2)]
buildmaxHeap(Heap)
for i in range(1, n+1):
    write(" " + str(Heap[i].key))
write("\n")

Solution (Python):
import sys
import math

from typing import List


def max_heapify(max_heap: List[int], ix: int) -> None:
    l_ix = ix * 2
    r_ix = ix * 2 + 1

    
    if l_ix < len(max_heap) and max_heap[l_ix] > max_heap[ix]:
        largest_ix = l_ix
    else:
        largest_ix = ix
    if r_ix < len(max_heap) and max_heap[r_ix] > max_heap[largest_ix]:
        largest_ix = r_ix

    if largest_ix != ix:
        max_heap[ix], max_heap[largest_ix] = max_heap[largest_ix], max_heap[ix]
        max_heapify(max_heap, largest_ix)


def build_max_heap(max_heap: List[int]) -> None:
    half = math.floor(len(max_heap) / 2)
    for i in reversed(range(1, half + 1)):
        max_heapify(max_heap, i)


_n = int(input())
max_heap = [int(i) for i in input().split()]
max_heap.insert(0, sys.maxsize)

build_max_heap(max_heap)
for val in max_heap[1:]:
    print(f' {val}', end='')
print()

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

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

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

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

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

def printHeap(H,Q,n):
    if H+1 == n:
        return
    print("node",n,end=": ")
    print("key =",Q[n],end=", ")
    print("parent key =",Q[int(n/2)],end=", ") if 1<n else None
    print("left key =",Q[2*n],end=", ") if 2*n<=H else None
    print("right key =",Q[2*n+1],end=", ") if 2*n+1<=H else None
    print()
    printHeap(H,Q,n+1)
    



H = int(input())
Q = list(map(int, input().split()))
Q.insert(0,-1)
buildMaxHeap(Q)
print(end=" ")
print(" ".join(map(str,Q[1:])))

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

def maxheapify(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:
        tmp = A[i]
        A[i] = A[largest]
        A[largest] = tmp
        maxheapify(largest)


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

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

Solution (Python):
class MaxHeap:
    def __init__(self):
        self.heap = []
        self.length = 0

    def __str__(self):
        return " " + " ".join(str(n) for n in self.heap)

    def up_insert(self, key):
        self.heap.append(key)
        self._upheap()
        self.length += 1

    def down_insert(self, key):
        self.heap.append(key)
        self.length += 1
        for i in range(self.length // 2, -1, -1):
            self._downheap(i)

    def down_many_insert(self, key):
        self.heap.extend(key)
        self.length += len(key)
        for i in range(self.length // 2, -1, -1):
            self._downheap(i)


    def _upheap(self):
        index = self.length - 1
        while True:
            parent_index = (index - 1) // 2
            if parent_index < 0 or self.heap[parent_index] >= self.heap[index]:
                break
            self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
            index = parent_index

    def _downheap(self, index):
        while True:
            child_index_left, child_index_right = index * 2 + 1, index * 2 + 2
            
            if child_index_left >= self.length:
                break
            elif (child_index_right >= self.length or self.heap[child_index_left] > self.heap[child_index_right]) and self.heap[index] < self.heap[child_index_left]:
                self.heap[index], self.heap[child_index_left] = self.heap[child_index_left], self.heap[index]
                index = child_index_left
            elif (child_index_right < self.length and self.heap[child_index_left] < self.heap[child_index_right]) and self.heap[index] < self.heap[child_index_right]:
                self.heap[index], self.heap[child_index_right] = self.heap[child_index_right], self.heap[index]
                index = child_index_right
            else:
                break



a = MaxHeap()
length = int(input())
t = [int(n) for n in input().split(" ")]
a.down_many_insert(t)
print(a)

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

def buildMaxHeap(A):
    for i in range(n//2, 0, -1):
        maxHeapify(A, i)
    
if __name__ == "__main__":
    n = int(input())
    A = [None]
    A.extend(list(map(int, input().split())))
    buildMaxHeap(A)
    print(" " + ' '.join(map(str, A[1:])))

Solution (Python):
def max_heapify(nodes, idx):
    left_idx = idx * 2
    right_idx = idx * 2 + 1

    max_idx = idx

    if left_idx <= len(nodes) and nodes[left_idx-1] > nodes[max_idx-1]:
        max_idx = left_idx
    if right_idx <= len(nodes) and nodes[right_idx-1] > nodes[max_idx-1]:
        max_idx = right_idx

    if max_idx != idx:
        tmp = nodes[idx-1]
        nodes[idx-1] = nodes[max_idx-1]
        nodes[max_idx-1] = tmp
        max_heapify(nodes, max_idx)
    return


def build_maxheap(nodes):
    for i in range(1, len(nodes)//2 + 1)[::-1]:
        max_heapify(nodes, i)
    return


def main():
    num_node = int(input())
    nodes = [int(x) for x in input().split()]
    build_maxheap(nodes)
    print(" " + " ".join(map(str, nodes)))
    return


main()

Solution (Python):
import sys

H = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().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, -1):
        maxHeapify(A, i)

buildMaxHeap(A)
print('',' '.join(map(str,A)))

Solution (Python):



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

    if(l < len(heap) and heap[i] < heap[l]):
        largest=l
    if(r < len(heap) and heap[largest] < heap[r]):
        largest=r
    if(i!=largest):
        heap[i],heap[largest]=heap[largest],heap[i]
        max_heapify(heap,largest)






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

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

for i in range(1,n+1):
    print(f" {heap[i]}",end="")
print()

Solution (Python):
N = int(input())
*A, = map(int, input().split())
def heapify(i):
    l = 2*i+1; r = 2*i+2
    left = l < N and A[i] < A[l]
    right = r < N and A[i] < A[r]
    if left and right:
        if A[l] < A[r]:
            left = 0
        else:
            right = 0
    if left:
        A[i], A[l] = A[l], A[i]
        heapify(l)
    elif right:
        A[i], A[r] = A[r], A[i]
        heapify(r)


for i in range(N-1, -1, -1):
    heapify(i)
print("",*A)

Solution (Python):
import math

def max_heapify(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]
        max_heapify(A, largest)
        
        
def build_max_heap(A):
    for i in range(math.floor(len(A)-1), 0, -1):
        max_heapify(A, i)
        
H = int(input())
A = [None] + list(map(int, input().split()))
build_max_heap(A)

for a in A[1:]:
    print(f" {a}", end="")
print("")

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

def build_maxheap(A):
  i = len(A) // 2
  while i >= 1:
    max_heapify(A, i)
    i -= 1

if __name__ == '__main__':
  num_of_data = int(input())
  A = [int(x) for x in input().split()]
  A.insert(0, 0)

  build_maxheap(A)
  A = A[1:]
  print(' {0}'.format(' '.join(map(str, A))))

Solution (Python):




def swap(A, i, j):
    tmp = A[i]
    A[i] = A[j]
    A[j] = tmp


def heap_size(A):
    return len(A) - 1


def parent_node(k):
    return k // 2


def left_node(k):
    return 2 * k


def right_node(k):
    return 2 * k + 1


def max_heapify(A, i):
    l = left_node(i)
    r = right_node(i)

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

    if largest != i:
        swap(A, i, largest)
        max_heapify(A, largest)


def build_max_heap(A):
    for i in reversed(range(1, heap_size(A) // 2 + 1)):
        max_heapify(A, i)


def print_heap(A):
    for i in range(1, heap_size(A) + 1):
        print(" {}".format(A[i]), end="")
    print()


def main():
    _ = int(input())
    A = [None] + [int(x) for x in input().split()]

    build_max_heap(A)
    print_heap(A)


main()

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

    if l < n+1 and A[l] > A[i]:
        largest = l
    else:
        largest = i

    if r < n+1 and A[r] > A[largest]:
        largest = r
        
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, n, largest)

n = int(input())
A = [None] + [int(i) for i in input().split()]
for i in range(int(n/2), 0, -1):
    max_heapify(A, n, i)
print(" ", end="")
print(*A[1:], sep=" ")

Solution (Python):
def build_max_heap(n,a):
	for i in range(int(n/2),0,-1):
		max_heap(n,a,i)

def max_heap(n,a,i):
	l = i * 2
	r = i * 2 + 1
	larg = i
	if l <= n and a[i-1] < a[l-1]:
		larg = l
	if r <= n and a[larg-1] < a[r-1]:
		larg = r
	if larg != i:
		tmp = a[larg-1]
		a[larg-1] = a[i-1]
		a[i-1] = tmp
		max_heap(n,a,larg)		

n = int(input())
a = list(map(int,input().split()))
build_max_heap(n,a)
for i in range(n):
	print(' ' + str(a[i]), end='')
print()

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 not 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 = [int(i) for i in input().split()]
A = [0] + A
buildMaxHeap(A, H)
tmp = ""
for i in A[1:]:
    tmp+= " " + str(i)
print(tmp)

Solution (Python):
def maxHeapfy(a, h, 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]
        maxHeapfy(a, h, largest)


h = int(input())
a = [-1]
a.extend([int(v) for v in input().split()])

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

print(' ' + ' '.join([str(v) for v in a[1:]]))

Solution (Python):

from math import floor

def parent(i):
    p_id = floor(i/2)
    if p_id > 0: return p_id
    else: return 0

def left(H,i):
    l_id = 2 * i
    if 0 < l_id < H: return l_id
    else: return 0

def right(H,i):
    r_id = 2 * i + 1
    if 0 < r_id < H: return r_id
    else: return 0

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

def max_heapify(A,i):
    H = len(A)
    l = left(H,i)
    r = right(H,i)
    largest = 0
    if 1 <= H and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= H and A[r] > A[largest]:
        largest = r
    if not largest == i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

H = int(input())
heap = [-2000000001]*(H+1)
for i,k in enumerate(input().split()):
    heap[i+1] = int(k)

build_max_heap(heap)

for i,h in enumerate(heap):
    if i == 0: continue
    print(' {0}'.format(h), end='')
print()