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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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:  # iが子供に降るときは、
        A[i], A[largest] = A[largest], A[i]
        max_heapify(largest)  # ここでいうlargestは、元々はiの子ノード。戦いに敗れたA[i]が格納されている。


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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/9/ALDS1_9_B
# heapの完全二分木としての表現は二分探索木のときとルールが違いのでこんがらがらないように注意
# 詳しくはP233と238の図
# 勉強にはなるが解くだけならpythonのライブラリでok
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:
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]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ALDS1_9_B Maximum Heap
import sys

def maxheap(A, i):
    # 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)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
    # print(i)
    # print(A_list)
    maxHeapify(i)
for i in range(1, H+1):
    print(" ", A_list[i], sep="", end="")
print("")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# vim: set fileencoding=utf-8:
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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H = int(input())
A = [0]
# A = [int(i) for i in input().split()]
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:]]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
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)
#        print(r,l,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]
#            print(i,r,l,largest)            
            self.swap(A,largest,size)
#        print(i,r,l,largest)
mh = MaxHeap(H)
for i in range(H):
    mh.swap(A,H-i,H)
A = map(str,A)
print(' '.join(A))

Submission status: Accepted

Solution code:
# coding: utf-8

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

Submission status: Accepted

Solution code:
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 #index of left child
    r = 2*i + 1 #right child
    H = len(A)-1 #heap size, A[0] is not used therefore -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")

Submission status: Accepted

Solution code:
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)
# print(max_heap)
build_max_heap(max_heap)
for val in max_heap[1:]:
    print(f' {val}', end='')
print()

Submission status: Accepted

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

Submission status: Accepted

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