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:
class MaxHeap():
    def __init__(self, a, h):
        self.a = a
        self.h = h
    def parent(self, i):
        return i//2
        
    def left(self, i):
        return 2 * i

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

    def maxHeapify(self, a, i):
        l = self.left(i)
        r = self.right(i)
        if l <= self.h and a[l] > a[i]:
            largest = l
        else:
            largest = i
        if r <= self.h and a[r] > a[largest]:
            largest = r
        if largest != i:
            a[i], a[largest] = a[largest], a[i]
            self.maxHeapify(a, largest)

    def buildMaxHeap(self, a):
        for i in range(self.h//2, 0, -1):
            self.maxHeapify(a, i)
        return a

if __name__ == '__main__':
    n = int(input().rstrip())
    a = [-1]
    a += [int(i) for i in input().rstrip().split(" ")]
    x = MaxHeap(a, n)
    for i in x.buildMaxHeap(x.a)[1:]:
        print("", i, end = "")
    print()

Submission status: Accepted

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


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

input()
A = list(map(int, input().split()))
build_max_heap(A)
print('', *A)

Submission status: Accepted

Solution code:
def maxHeapfy(A, 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:
        A[i], A[largest] = A[largest], A[i]
        maxHeapfy(A, largest)

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


H = int(input())

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

buildMaxHeap(A, H)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

n = int(raw_input())
l = map(int, raw_input().split())
A = [0]
for i in range(n):
    A.append(l[i])
buildMaxHeap(A)
print " "+" ".join(map(str, A[1:]))

Submission status: Accepted

Solution code:
H = int(input())
A = [None] + list(map(int, input().split()))

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

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

build_max_heap(A)
print(" ", end = "")
print(*A[1:])

Submission status: Accepted

Solution code:
import sys

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

    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)

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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    buildMaxHeap(A)
    print " " + " ".join(map(str, A))

Submission status: Accepted

Solution code:
#coding:utf-8
#1_9_B
def max_heapify(heap, i):
    l = (i+1)*2 - 1
    r = (i+1)*2

    if l < len(heap) and heap[l] > heap[i]:
        largest = l
    else:
        largest = i
    if r < len(heap) and heap[r] > heap[largest]:
        largest = r

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

def build_max_heap(heap):
    for i in reversed(range(0, len(heap)//2 + 1)):
            max_heapify(heap, i)
    return heap

size = int(input())
heap = list(map(int, input().split()))
for node in build_max_heap(heap):
    print(" {}".format(node), end="")
print()

Submission status: Accepted

Solution code:
class max_heap:
    def __init__(self, vals):
        self.vals=vals
        self.index_max = len(self.vals)

    def size(self):
        return self.index_max

    def check(self, i):
        assert(i >= 1)
        assert(i <= self.index_max)

    def val_at(self, i):
        self.check(i)
        return self.vals[i-1]

    def left_idx(self, i):
        self.check(i)
        t = 2*i
        if t <= self.index_max:
            return t
        else:
            return None

    def right_idx(self, i):
        self.check(i)
        t = 2*i + 1
        if t <= self.index_max:
            return t
        else:
            return None

    def parent_idx(self, i):
        self.check(i)
        t = i//2
        if t > 0:
            return t
        else:
            return None

    def swap(self, i, j):
        self.check(i); self.check(j)
        self.vals[i-1], self.vals[j-1] = self.vals[j-1], self.vals[i-1]

    def max_heapify(self, i):
        self.check(i)
        l_idx = self.left_idx(i)
        r_idx = self.right_idx(i)
        swap_target = None

        if (l_idx is not None) and (self.val_at(l_idx) > self.val_at(i)):
            swap_target = l_idx
            # print('leftval, ival  ', self.val_at(l_idx), self.val_at(i), self.val_at(l_idx)>self.val_at(i))
            if r_idx is not None and self.val_at(r_idx) > self.val_at(l_idx):
                swap_target = r_idx
        elif r_idx is not None and self.val_at(r_idx) > self.val_at(i):
            swap_target = r_idx

        if swap_target is not None:
            # print('swap:', i, swap_target)
            self.swap(i, swap_target)
            self.max_heapify(swap_target)

    def build_max_heap(self):
        for i in reversed(range(1, self.size()//2+1)):
            # print('tgt: ', i)
            # print(self.vals)
            self.max_heapify(i)

    def show(self):
        return ''.join(map(lambda x: ' '+str(x), self.vals))


if __name__ == "__main__":
    H = int(input())   # in [1, 500,000]
    vals_str = input()   # |val|<=2,000,000,000 = 2e9
    vals = list(map(int, vals_str.split(' ')))
    mh = max_heap(vals)
    mh.build_max_heap()
    print(mh.show())

Submission status: Accepted

Solution code:
def get_item(L,i): return L[i] if len(L) > i else -2*10**9-1
def left (i): return i*2
def right(i): return i*2 + 1

def maxHeapify(A,i):
    l = left(i)
    r = right(i)
    largest = i
    if get_item(A,l) > A[largest]: largest = l
    if get_item(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(len(A)//2,0,-1): maxHeapify(A,i)


if __name__=='__main__':
    H = int(input())
    hp = [0] + list(map(int,input().split()))
    buildMaxHeap(hp)
    print("",*hp[1:])

Submission status: Accepted

Solution code:
def upheap(a,i):
    if i == 0: return
    while i > 0:
        p = (i+1)/2-1
        if a[p] < a[i]:
            a[p],a[i]=a[i],a[p]
        i = p

def heapify(a,i):
    lid = (i+1)*2-1
    rid = (i+1)*2
    maxc = -1
    if lid < len(a):
        maxc = lid
    if rid < len(a):
        if a[maxc] < a[rid]:
            maxc = rid
    if maxc != -1:
        if a[i] < a[maxc]:
            a[i],a[maxc]=a[maxc],a[i]
            heapify(a,maxc)


def build_heap(a):
    for i in range(len(a)):
        j = len(a)-1-i # n-1 to 0
        heapify(a,j)

n = int(raw_input())
a = map(int,raw_input().split(' '))
build_heap(a)
print '',
print ' '.join(map(str,a))

Submission status: Accepted

Solution code:
# -*- coding: utf_8 -*-

def maxHeapify(A, i):
    l = 2 * i - 1
    r = 2 * i
    largest = i - 1

    if l < len(A):
        largest = largest if A[largest] > A[l] else l

    if r < len(A):
        largest = largest if A[largest] > A[r] else r

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

if __name__ == "__main__":
    H = int(input())
    a = [int(x) for x in input().split()]

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

    print(" " + " ".join(str(x) for x in a)),

Submission status: Accepted

Solution code:
import math

def parent(i):
    return math.floor(i / 2)

def left(i):
    return 2 * i

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

def get_largest(A, n, i):
    l = left(i)
    r = right(i)
    largest = None
    if l <= n and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= n and A[largest] < A[r]:
        largest = r
    return largest


def max_heapify(A, n, i):
    largest = get_largest(A, n, i)
    x = i
    while largest is not x:
        tmp = A[x]
        A[x] = A[largest]
        A[largest] = tmp
        x = largest
        largest = get_largest(A, n, x)

def build_max_heap(A, n):
    for i in reversed(range(1, math.floor(n/2) + 1)):
        max_heapify(A, n, i)

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

build_max_heap(heap, n)

ans = ''
for i in heap[1:]:
    ans += ' {}'.format(str(i))
print(ans)

Submission status: Accepted

Solution code:
import math

def parent(i):
    return math.floor(i / 2)

def left(i):
    return 2 * i

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

def get_largest(A, n, i):
    l = left(i)
    r = right(i)
    largest = None
    if l <= n and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= n and A[largest] < A[r]:
        largest = r
    return largest


def max_heapify(A, n, i):
    largest = get_largest(A, n, i)
    x = i
    while largest is not x:
        tmp = A[x]
        A[x] = A[largest]
        A[largest] = tmp
        x = largest
        largest = get_largest(A, n, x)

def build_max_heap(A, n):
    for i in range(math.floor(n/2), 0, -1):
        max_heapify(A, n, i)

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

build_max_heap(heap, n)

ans = ''
for i in heap[1:]:
    ans += ' {}'.format(str(i))
print(ans)

Submission status: Accepted

Solution code:
import math

def parent(i):
    return math.floor(i / 2)

def left(i):
    return 2 * i

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

def get_largest(A, n, i):
    l = left(i)
    r = right(i)
    largest = None
    if l <= n and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= n and A[largest] < A[r]:
        largest = r
    return largest


def max_heapify(A, n, i):
    largest = get_largest(A, n, i)
    x = i
    while largest is not x:
        tmp = A[x]
        A[x] = A[largest]
        A[largest] = tmp
        x = largest
        largest = get_largest(A, n, x)

def build_max_heap(A, n):
    for i in range(math.floor(n/2), 0, -1):
        max_heapify(A, n, i)

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

build_max_heap(heap, n)

print(' ', end='')
print(*heap[1:])

Submission status: Accepted

Solution code:
h = int(input())
heap = list(map(int, input().split()))
 
 
def max_heapify(a, i):
    li, ri = i * 2 + 1, i * 2 + 2
    if li < h:
        largest = li
        if ri < h and a[ri] > a[li]:
            largest = ri
        if a[largest] > a[i]:
            a[i], a[largest] = a[largest], a[i]
            max_heapify(a, largest)
 
 
def build_max_heap(a):
    for i in range((h - 1) // 2, -1, -1):
        max_heapify(a, i)
 
 
build_max_heap(heap)
 
print(' ', end='')
print(*heap)

Submission status: Accepted

Solution code:


def  maxHeapify(i):
    l =2*i
    r = 2*i+1
    # print(A[i])
    largest =0
    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)
    # print(A)



H = int(input())

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

A = [-1]+A

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

Astr = list(map(str,A))

print(" ",end="")

print(*A[1:])

Submission status: Accepted

Solution code:


def  maxHeapify(i):
    l =2*i
    r = 2*i+1
    # print(A[i])
    largest =0
    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)
    # print(A)



H = int(input())

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

A = [-1]+A

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

Astr = list(map(str,A))

print(" ",end="")

print(" ".join(Astr[1:]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def max_heapify(index):
    left, right, largest = 2 * index, 2 * index + 1, -1

    if left <= array_length and array[left] > array[index]:
        largest = left
    else:
        largest = index

    if right <= array_length and array[right] > array[largest]:
        largest = right

    if largest != index:
        array[index], array[largest] = array[largest], array[index]
        max_heapify(largest)

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    # assert len(array) == array_length

    array.insert(0, None)
    for j in range(array_length // 2, 0, -1):
        max_heapify(j)
    print('', end=' ')
    print(*array[1:])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def max_heapify(index):
    left, right, largest = 2 * index, 2 * index + 1, -1

    if left <= array_length and array[left] > array[index]:
        largest = left
    else:
        largest = index

    if right <= array_length and array[right] > array[largest]:
        largest = right

    if largest != index:
        array[index], array[largest] = array[largest], array[index]
        max_heapify(largest)

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    # assert len(array) == array_length

    # array.insert(0, None)
    array = [None] + array
    for j in range(array_length // 2, 0, -1):
        max_heapify(j)
    print('', end=' ')
    print(*array[1:])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def max_heapify(index):
    left, right, largest = 2 * index, 2 * index + 1, -1

    if left <= array_length and array[left] > array[index]:
        largest = left
    else:
        largest = index

    if right <= array_length and array[right] > array[largest]:
        largest = right

    if largest != index:
        array[index], array[largest] = array[largest], array[index]
        max_heapify(largest)

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    # assert len(array) == array_length

    array.insert(0, None)
    for j in range(array_length // 2, 0, -1):
        max_heapify(j)
    print('', *array[1:])

Submission status: Accepted

Solution code:
#coding:UTF-8
def maxHeapify(A,i,n):
    l=2*i
    r=2*i+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,n)

def MH(A,n):
    for i in range(int(n/2),0,-1):
        maxHeapify(A,i,n)
    A.remove(-1)
    for i in range(len(A)):
        A[i]=str(A[i])
    print(" "+" ".join(A))        
if __name__=="__main__":
    H=int(input())
    A=input().split(" ")
    for i in range(len(A)):
        A[i]=int(A[i])
    A=[-1]+A
    MH(A,H)

Submission status: Accepted

Solution code:
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:
        temp = A[i]
        A[i] = A[largest]
        A[largest] = temp
        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) # ?????????1??????????????????????????????????????????

    # ???????????????
    build_maxheap(A)
    A = A[1:]  # ???????????????????????????

    # ???????????????
    print(' {0}'.format(' '.join(map(str, A))))

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_B
#???????????? 17:55~

def maxHeapify(heap, index):
    left_index = 2 * index
    right_index = 2 * index + 1

    if left_index < len(heap) and heap[left_index] > heap[index]:
        largest_index = left_index
    else:
        largest_index = index

    if right_index < len(heap) and heap[right_index] > heap[largest_index]:
        largest_index = right_index

    if not largest_index == index:
        heap[index], heap[largest_index] = heap[largest_index], heap[index]
        maxHeapify(heap, largest_index)
    
def main():
    n_node = int(input())
    target_list = [""] + [int(n) for n in input().split()]
    for i in range(1, int(len(target_list) / 2) + 1)[::-1]:
        maxHeapify(target_list, i)
        
    print(*target_list)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_B
#???????????? 17:55~

def maxHeapify(heap, index):
    left_index = 2 * index
    right_index = 2 * index + 1

    if left_index < len(heap) and heap[left_index] > heap[index]:
        largest_index = left_index
    else:
        largest_index = index

    if right_index < len(heap) and heap[right_index] > heap[largest_index]:
        largest_index = right_index

    if largest_index != index:
        heap[index], heap[largest_index] = heap[largest_index], heap[index]
        maxHeapify(heap, largest_index)
    
def main():
    n_node = int(input())
    target_list = [""] + [int(n) for n in input().split()]
    for i in range(1, int(len(target_list) / 2) + 1)[::-1]:
        maxHeapify(target_list, i)
        
    print(*target_list)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_B
#???????????? 17:55~

def maxHeapify(heap, index):
    left_index = 2 * index
    right_index = 2 * index + 1
    largest_index = index
    
    if left_index < len(heap) and heap[left_index] > heap[index]:
        largest_index = left_index

    if right_index < len(heap) and heap[right_index] > heap[largest_index]:
        largest_index = right_index

    if largest_index != index:
        heap[index], heap[largest_index] = heap[largest_index], heap[index]
        maxHeapify(heap, largest_index)
    
def main():
    n_node = int(input())
    target_list = [""] + [int(n) for n in input().split()]
    for i in range(1, int(len(target_list) / 2) + 1)[::-1]:
        maxHeapify(target_list, i)
        
    print(*target_list)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def maxHeapify(H, A, 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(H, A, largest)

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

H = int(input())
A = [None] + [int(a) for a in input().split()]

buildMaxHeap(H, A)

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

Submission status: Accepted

Solution code:
# tige????????????????????????

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:
def maxHeapify(heap, i):
    left = (i + 1) * 2 - 1
    right = (i + 1) * 2
    largest = left if left < len(heap) and heap[left] > heap[i] else i
    largest = right if right < len(heap) and heap[right] > heap[largest] else largest
    if largest != i:
        heap[i], heap[largest] = heap[largest], heap[i]
        maxHeapify(heap, largest)

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

n = int(input())
heap = list(map(int, input().split()))
buildMaxHeap(heap)

out = ''
for key in heap:
    out += (' {}'.format(str(key)))
print(out)

Submission status: Accepted

Solution code:
global A

def max_heapfy(i):
    left = 2*i+1
    right = 2*i+2

    max_val = 0
    if left< H and A[i] < A[left]:
        max_val = left
    else:
        max_val = i

    if right<H and A[max_val] < A[right]:
        max_val = right

    if max_val != i:
        temp = A[i]
        A[i] = A[max_val]
        A[max_val] = temp
        max_heapfy(max_val)

if __name__ == '__main__':
    global H
    H = int(input())
    A = [int(i) for i in input().split()]
    for i in reversed(range(H//2)):
        max_heapfy(i)

    for a in A:
        print(" {}".format(a),end='')
    print('')

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
class Heap:
    def __init__(self, L):
        self.H = len(L)
        self.heap = L
        self.heap.insert(0, 0)

    def parent(self, i):
        return i // 2

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

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

    def maxHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        if l <= H and self.heap[l] > self.heap[i]:
            largest = l
        else:
            largest = i

        if r <= H and self.heap[r] > self.heap[largest]:
            largest = r

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

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


H = int(input())
L = list(map(int, input().split()))
heap = Heap(L)
heap.buildMaxHeap()
heap.heap.pop(0)
print(' ' + ' '.join([str(a) for a in heap.heap]))

Submission status: Accepted

Solution code:
H = int(input())
A = [None] + [int(i) for i in input().split()]

def maxHeapify(H, A, i):
    left = 2*i
    right = left + 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(H,A,largest)

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

buildmaxHeap(H,A)

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

Submission status: Accepted

Solution code:
class Heap(list):
    def __init__(self, init_list = []):
        super().__init__(init_list)

    @staticmethod
    def left(i: int) -> int:
        return 2 * i + 1

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

    def max_heapify(self, i: int):
        l = self.left(i)
        r = self.right(i)
        H = len(self)
        # ????????????????????????????????§???????????§????????????????????¶
        if l < H and self[l] > self[i]:
            largest = l
        else:
            largest = i
        if r < H and self[r] > self[largest]:
            largest = r
        if largest != i:  # i ???????????????????????§????????´???
            # A[i] ??¨ A[largest] ?????????
            tmp = self[i]
            self[i] = self[largest]
            self[largest] = tmp
            self.max_heapify(largest)  # ?????°??????????????????

    def build_max_heap(self):
        for i in range(len(self)//2, -1, -1):
            self.max_heapify(i)

n = int(input())
xs = Heap([int(i) for i in input().split()])
xs.build_max_heap()
print(" " + " ".join([str(i) for i in xs] ))

Submission status: Accepted

Solution code:
def max_heapify(A, i):
  l = i * 2
  r = l + 1
  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:
    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)
 
H = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
build_max_heap(A)
 
print(" " + " ".join(map(str, A[1:])))

Submission status: Accepted

Solution code:
import sys

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

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

def get_parent(i):
    return int((i - 1) / 2)

def make_heap_tree(array, i, item_num):
    left = get_left(i)
    right = get_right(i)
    largest = i
    if (left < item_num) and (array[left] > array[largest]):
        largest = left
    if (right < item_num) and (array[right] > array[largest]):
        largest = right
    if largest != i:
        tmp = array[i]
        array[i] = array[largest]
        array[largest] = tmp
        make_heap_tree(array, largest, item_num)

def main():
    size = int(sys.stdin.readline().strip())
    array = map(lambda x: int(x), sys.stdin.readline().strip().split(" "))
    for i in reversed(range(0, get_parent(size) + 1)):
        make_heap_tree(array, i, size)
    print " " + " ".join(map(lambda x: str(x), array))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


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


if __name__ == "__main__":
    H = int(input())
    inp = list(map(int, input().split()))
    buildMaxHeap(inp)
    print(" " + " ".join(map(str, inp)))

Submission status: Accepted

Solution code:
import sys
H = input()

def main():
    A = map(int,raw_input().split())
    buildMaxHeap(A)
    for i in A:
        sys.stdout.write(" {}".format(i))
    print ""

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def swap(A, x, y):
    i = A[x]
    A[x] = A[y]
    A[y] = i

def left(i):
    return i * 2

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

def  maxHeapify(A, 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: #// i ???????????????????????§????????´???
        swap(A, i, largest) # ??????
        maxHeapify(A, largest, H) # ?????°??????????????????

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

def main():

    """ ????????? """
    H = int(input().strip())
    A = [""]
    A.extend(list(map(int,input().split())))
    buildMaxHeap(A, H)
    print(" {}".format(" ".join(map(str,A[1:]))))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

N = int(input())
H = list(map(int, input().split()))
ans = []

a = [(-x, x) for x in H]
heapq.heapify(a)

for i in range(N):
    print(" {}".format(a[i][1]), end = "")
print()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from math import floor
sys.setrecursionlimit(100000)

N = int(input())
A = [None] + [int(n) for n in input().split()]

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

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

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