1
"""
2
二叉堆
3
二叉堆的逻辑结构是完全二叉树,实际上是由1为起点的一维数组表示。
4
给定一个节点的下标`i`,其父节点`parent(i)=1/2`、左子节点`left(i)=2*i`、右子节点`right(i)=2*i+1`。
5
最大堆性质：节点的键值小于等于其父节点的键值。最大堆堆根中存储着最大的值。
6
最小堆性质：节点的键值大于等于其父节点的键值。最小堆的根中存储着最小的值。
7
"""
8
def parent(i):
9
    return i//2
10

11
def left(i):
12
    return i*2
13

14
def right(i):
15
    return i*2+1
16

17
def solve():
18
    """
19
    5
20
    7 8 1 2 3
21
    node 1: key = 7,  left key = 8,  right key = 1,
22
    node 2: key = 8,  parent key = 7,  left key = 2,  right key = 3,
23
    node 3: key = 1,  parent key = 7,
24
    node 4: key = 2,  parent key = 8,
25
    node 5: key = 3,  parent key = 8,
26
    """
27
    H = int(input())
28
    array = [0]
29
    array.extend(list(map(int,input().split())))
30
    for i in range(1,H+1):
31
        print('node {}: key = {}, '.format(i,array[i]),end=' ')
32
        if parent(i) >= 1:
33
            print('parent key = {}, '.format(array[parent(i)]),end=' ')
34
        if left(i) <= H:
35
            print('left key = {}, '.format(array[left(i)]),end=' ')
36
        if right(i) <= H:
37
            print('right key = {}, '.format(array[right(i)]),end='')
38
        print()
39

40
if __name__ == '__main__':
41
    solve()

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

5
16, 14, 10, 8, 7, 9, 3, 2, 4, 1
6
"""
7
def left(i):
8
    return i*2
9

10
def right(i):
11
    return i*2+1
12

13
H = 0
14

15
def maxHeapify(A,i):
16
    """
17
    用于从根节点i向叶节点方向寻找A[i]值的恰当位置,从而使以i为根节点的子树成为最大堆。这里我们假设堆的大小为H
18
    """
19
    l = left(i)
20
    r = right(i)
21
    largest = None
22
    if l <= H and A[l] > A[i]:
23
        largest = l
24
    else:
25
        largest = i
26

27
    if r <= H and A[r] > A[largest]:
28
        largest = r
29

30
    if largest != i :
31
        A[i],A[largest] = A[largest],A[i]
32
        maxHeapify(A,largest) # 递归调用
33

34
def buildMaxHeap(A):
35
    for i in range(H//2,0,-1):
36
        # print('i=',i)
37
        maxHeapify(A,i)
38

39
if __name__ == '__main__':
40
    H = int(input())
41
    A = [0]
42
    A.extend(list(map(int,input().split())))
43
    buildMaxHeap(A)
44
    print(A)