Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

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 &ne; 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.



Sample input:
10
4 1 3 2 16 9 10 14 8 7


Sample output:
 16 14 10 8 7 9 3 2 4 1

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)
#         print(A)
    
    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])))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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:])))

Submission status: Accepted

Solution code:

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

    largest = i

    if l < len(A):
        if A[i] < A[l]:
            largest = l
            # print("l", A[l])

    
    if r < len(A):
        if A[largest] < A[r]:
            largest = r
            # print("l", A[r])
    
    if largest != i: #子の方が親より大きい
        tmp = A[i]
        # print(A[largest])
        A[i] = A[largest]
        A[largest] = tmp

        MaxHeap(A, largest)

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

    for k in range(length, 0, -1):
        #print(k)
        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 
"""

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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:])

Submission status: Accepted

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

def maxHeapify(A, i):
    #สููตร heap หาตำแหน่งตัวซ้ายกับขวา
    l = 2*i
    r = 2*i+1
    #เทียบ 2 ตัวตามตำแหน่ง
    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]
        #เรีียกอีกรอบ
        #ทำจนกว่า max สุดจะอยู่บนแล้ว เอาnodeสุดท้ายของtreeเข้ามา swap แทน
        #จากนั้น remove maxออกไปเก็บ 
        maxHeapify(A, largest)

def buildMaxHeap(A):
    #ตั้งแต่ตำแหน่ง กลาง ถึง 0 เรียงด้านซ้ายก่อน
    for i in range(H//2,0,-1):
        maxHeapify(A, i)

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

Submission status: Accepted

Solution code:
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:])))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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:])

Submission status: Accepted

Solution code:
h = int(input())
A = list(map(int, input().split()))
A.insert(0, 0) # 1-origin

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:]]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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("")

Submission status: Accepted

Solution code:
# 最大ヒープ Maximum heap


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

Submission status: Accepted

Solution code:
# Maximum heap

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:])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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:])))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
def max_heapify(A, idx):
    left = (idx+1)*2-1
    right = (idx+1)*2
    #print('idx={}, left={}, right={}'.format(idx, left, right))
    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):
    #print(*A)
    for i in range(len(A)//2, -1, -1):
        max_heapify(A, i)
        #print('{}:'.format(i), *A)
    
n = int(input())

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

build_max_heap(a)

print('', *a)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys

def maxHeapify(heap, i):
    h = len(heap) - 1 # 1 origin
    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 # 1 origin
    for i in range(h//2, 0, -1):
        maxHeapify(heap, i)

# sys.stdin = open('input.txt')

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

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

Submission status: Accepted

Solution code:
import copy

n = int(input())
nodes = list(map(int, input().split()))
heap = copy.deepcopy(nodes)
heap.insert(0, None)
# in case if the right node of the last tree is None
MIN_INF = -10 ** 10
heap.append(MIN_INF)
# heap starts with 1, 2, 3, ... n

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)

  # print(heap)

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

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

Submission status: Accepted

Solution code:
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
    #print(x,l,r)
    
    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)

Submission status: Accepted

Solution code:
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])))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    H = int(input())

    # 1オリジンにするために、0番目にNoneを入れておく
    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] # pythonはこれで要素の入れ替えが可能
            max_heapify(largest)

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

    # Aが1オリジンなので、0番目は出力しないように
    print(' ' + ' '.join(map(str, A[1:])))

Submission status: Accepted

Solution code:
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))))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# Makimam Heap
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:])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
import math

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

	if l <= main[0] and main[l] > main[s]:
			#print("Left: " +str(main[l]) + ":" + str(l))
			largest = l
	else:
		largest = s
	if r <= main[0] and main[r] > main[largest]:
		#print("Right: "+ str(main[r]) + ":" + str(r))
		largest = r

	if largest != s:
		#print("move node:" + str(largest) + " " + str(main[largest]))

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

#print(main)

del n

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

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

print()

Submission status: Accepted

Solution code:
"""
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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:])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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:])))

Submission status: Accepted

Solution code:

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("")