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: Wrong Answer

Solution code:
import pprint as pp

class Main():
    def exchange(self, n1, n2):
        tmp = self.A[n1]
        self.A[n1] = self.A[n2]
        self.A[n2] = tmp

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

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

    def maxHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        if l <= self.H and self.A[l] > self.A[i]:
            largest = l
        else :
            largest = i
        if r <= self.H and self.A[r] > self.A[largest]:
            largest = r
        if largest != i:
            self.exchange(i, largest)
            self.maxHeapify(largest) # 再帰的に呼び出し

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

    def main(self):
        self.H = int( input() )
        self.A = [0]
        inputData = [int(x) for x in input().split()]
        self.A.extend(inputData)
        self.buildMaxHeap()
        for i in range(1, self.H+1):
            print(" " + str(self.A[i]), end = "" )

if __name__ == '__main__':
    M = Main()
    M.main()

Submission status: Wrong Answer

Solution code:
def get_left_index(A, i):
    if len(A) > 2 * i:
        return 2 * i
    else:
        return None

def get_right_index(A, i):
    if len(A) > 2 * i + 1:
        return 2 * i + 1
    else:
        return None

def max_heapfy(A, i):
    left = get_left_index(A, i)
    right = get_right_index(A, i)
    largest = i
    if left and A[left] > A[i]:
        largest = left
    if right and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapfy(A, largest)

H = int(input())
A = [0]
for elem in map(int, input().split()):
    A.append(elem)


def build_max_heap(A):
    for i in range(H//2, 0, -1):
        print(i)
        max_heapfy(A, i)
build_max_heap(A)
print(' ', end='')        
print(*A[1:])

Submission status: Wrong Answer

Solution code:
import sys

if __name__ == '__main__':
	n = sys.stdin.readline()
	n = int(n)
	arr = sys.stdin.readline()
	arr = map(lambda x : int(x), arr.split())
	print ' ' + ' '.join(map(lambda x: str(x), sorted(arr)[::-1]))

Submission status: Wrong Answer

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 reversed(range(1, int(H / 2))):
		max_heapify(A, i)

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

Submission status: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

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(" ".join(Astr[1:]))

Submission status: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

Solution code:
print(1,2,3)

Submission status: Wrong Answer

Solution code:
#coding:UTF-8
def maxHeapify(A,i,n):
    print(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,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: Wrong Answer

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(int(len(target_list) / 2), 0, -1):
        print(i)
        maxHeapify(target_list, i)
        
    print(*target_list)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def maxHeapify(heap, i):
    while (i + 1) * 2 <= len(heap):
        left = (i + 1) * 2 - 1
        right = (i + 1) * 2
        if heap[i] < heap[left]:
            tmp = heap[i]
            heap[i] = heap[left]
            heap[left] = tmp
            i = left
        elif heap[i] < heap[right]:
            tmp = heap[i]
            heap[i] = heap[right]
            heap[right] = tmp
            i = right
        else:
            break

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


n = int(input())
heap = list(map(int, input().split()))
buildMaxHeap(heap)
out = ''
for key in heap:
    out += ' str(key)'
print(out)

Submission status: Wrong Answer

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: Wrong Answer

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))):
        make_heap_tree(array, i, size)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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))):
        make_heap_tree(array, i, size)
    print " " + " ".join(map(lambda x: str(x), array))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def heapify(values):
  n = len(values)
  for i in range(1,n):
    upheap(values,i)
    print(' '.join(map(str, values)))

def upheap(values, i):
  while parent(i) >= 0:
    if values[i] > values[parent(i)]:
      values[i], values[parent(i)] = values[parent(i)], values[i]
      i = parent(i)
    else:
      break

def pop(values):
  ret = values[0]
  values[0], values[len(values)-1] = values[len(values)-1], values[0]
  del values[len(values)-1]
  downheap(values)
  return ret

def downheap(values):
  i = 0
  while left(i) < len(values) or right(i) < len(values):
    l = left(i)
    r = right(i)
    if l >= len(values):
      m = r
    elif r >= len(values):
      m = l
    else:
      m = r
      if values[l] > values[r]:
        m = l
    if values[i] < values[m]:
      values[m], values[i] = values[i], values[m]
    i = m

def parent(i):
  i = i+1
  return i//2-1

def left(i):
  i = i+1
  return i*2-1

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


n = int(input())
a = list(map(int,input().split(' ')))

heapify(a)
print(' '.join(map(str, a)))

Submission status: Wrong Answer

Solution code:
h = int(input())
key = list(map(int,input().split()))
key.sort()
key.reverse()

print("",*key)

Submission status: Wrong Answer

Solution code:
def maxHeapify(A,i,H):
    l=2*i
    r=2*i+1
    #select the node which has the maximum value
    if l<=H and A[l-1]>A[i-1]:
        largest=l
    else:
        largest=i
    if r<=H and A[r-1]>A[l-1]:
        largest=r
    
    #value of children is larger than that of i
    if largest!=i:
        A[i-1],A[largest-1]=A[largest-1],A[i-1]
        maxHeapify(A,largest,H)

if __name__=='__main__':
    H=int(input())
    A=list(map(int,input().split()))
    print(A)
    for i in range(H//2,0,-1):
        maxHeapify(A,i,H)
    print(A)

Submission status: Wrong Answer

Solution code:
def maxHeapify(A,i,H):
    l=2*i
    r=2*i+1
    #select the node which has the maximum value
    if l<=H and A[l-1]>A[i-1]:
        largest=l
    else:
        largest=i
    if r<=H and A[r-1]>A[l-1]:
        largest=r
    
    #value of children is larger than that of i
    if largest!=i:
        A[i-1],A[largest-1]=A[largest-1],A[i-1]
        maxHeapify(A,largest,H)

if __name__=='__main__':
    H=int(input())
    A=list(map(int,input().split()))
    print(A)
    for i in range(H//2,0,-1):
        maxHeapify(A,i,H)
    print(*A)

Submission status: Wrong Answer

Solution code:
def maxHeapify(A,i,H):
    l=2*i
    r=2*i+1
    #select the node which has the maximum value
    if l<=H and A[l-1]>A[i-1]:
        largest=l
    else:
        largest=i
    if r<=H and A[r-1]>A[l-1]:
        largest=r
    
    #value of children is larger than that of i
    if largest!=i:
        A[i-1],A[largest-1]=A[largest-1],A[i-1]
        maxHeapify(A,largest,H)

H=int(input())
A=list(map(int,input().split()))
for i in range(H//2,0,-1):
    maxHeapify(A,i,H)
print(A)

Submission status: Wrong Answer

Solution code:
def maxHeapify(A,i,H):
    l=2*i
    r=2*i+1
    #select the node which has the maximum value
    if l<=H and A[l-1]>A[i-1]:
        largest=l
    else:
        largest=i
    if r<=H and A[r-1]>A[l-1]:
        largest=r
    
    #value of children is larger than that of i
    if largest!=i:
        A[i-1],A[largest-1]=A[largest-1],A[i-1]
        maxHeapify(A,largest,H)
        
H=int(input())
A=list(map(int,input().split()))
for i in range(H//2,0,-1):
    maxHeapify(A,i,H)
    
print(" {}".format(" ".join(map(str,A))))

Submission status: Wrong Answer

Solution code:
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if r<H:
  if A[i]<A[l]:g=l
  if A[i]<A[r]:g=r
  if g>i:A[i],A[g]=A[g],A[i];h(g)
 elif l<H and A[i]<A[l]:
  A[i],A[l]=A[l],A[i];h(l)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))


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

h = (n - 1) // 2
for i in reversed(range(h)):
    maxheapify(a, i)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))


def maxheapify(a, i):
    l = i*2 + 1
    r = i*2 + 2
    
    if r < n:
        if a[l] > a[i]:
            largest = l
        else:
            largest = i
        if a[r] > a[largest]:
            largest = r

        if largest != i:
            memo = a[i]
            a[i] = a[largest]
            a[largest] = memo
            maxheapify(a, largest)
    
    elif l < n:
        if a[l] > a[i]:
            largest = l
        else:
            largest = i
        if largest != i:
            memo = a[i]
            a[i] = a[largest]
            a[largest] = memo
            maxheapify(a, largest)

h = (n - 1) // 2
for i in reversed(range(h)):
    maxheapify(a, i)

print("", *a)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun  9 13:21:18 2018
ALDS1-9b
@author: maezawa
"""
import math

h = int(input())
a = list(map(int,input().split()))

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

def left(node):
    return 2*node

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

def max_heapify(a, i):
    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]
        max_heapify(a, largest)

def build_max_heap(a):
    for i in list(range(1,h//2))[::-1]:
        max_heapify(a, i)
        #print(a)
        
build_max_heap(a)

for i in range(h):
    print(' {}'.format(a[i]),end = '')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun  9 13:21:18 2018
ALDS1-9b
@author: maezawa
"""
import math

h = int(input())
a = list(map(int,input().split()))

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

def left(node):
    return 2*node

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

def max_heapify(a, i):
    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]
        max_heapify(a, largest)

def build_max_heap(a):
    for i in list(range(1,h//2+1))[::-1]:
        max_heapify(a, i)
        #print(a)
        
build_max_heap(a)

for i in range(h):
    print(' {}'.format(a[i]))

Submission status: Time Limit Exceeded

Solution code:
def maxHeapify(heap, i):
    while (i + 1) * 2 <= len(heap):
        left = (i + 1) * 2 - 1
        right = (i + 1) * 2
        largest = left if heap[left] > heap[i] and left <= len(heap) else i
        largest = right if heap[right] > heap[largest] and right <= len(heap) 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 += ' str(key)'
print(out)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 g=A.index(max(A[i],A[i+(2*i<H)*i],A[i+(2*i+1<H)*(i+1)]))                      
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class PriorityQueue:
    def __init__(self):
        self.nodes = deque([])

    def max_heapify(self, i):
        if i >= len(self.nodes): return
        left, right = (i+1)*2-1, (i+1)*2

        largest = i
        if left < len(self.nodes) and self.nodes[i] < self.nodes[left]: largest = left
        if right < len(self.nodes) and self.nodes[largest] < self.nodes[right]: largest = right

        if largest != i:
            self.nodes[i], self.nodes[largest] = self.nodes[largest], self.nodes[i]
            self.max_heapify(largest)

    def print_element(self):
        for node in self.nodes:
            print('', node, end='')
        print('')

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

pq = PriorityQueue()
pq.nodes = deque(A)

for i in range((n-1)//2, -1, -1):
    pq.max_heapify(i)

pq.print_element()

Submission status: Accepted

Solution code:
n = int(input())
tree = list(map(int, input().split()))

def main() :
    createHeap(n)
    print('', ' '.join(map(str, tree)))

def createHeap(x):
    for i in range((x - 1) // 2, -1, -1) :
        maxHeap(i)

def maxHeap(i) :
    if i * 2 + 1 >= n:
        return

    tmp = i * 2 + 1

    if i * 2 + 2 < n :
        if tree[i * 2 + 1] < tree[i * 2 + 2] :
            tmp = i * 2 + 2

    if tree[i] < tree[tmp] :
        tree[i], tree[tmp] = tree[tmp], tree[i]
        maxHeap(tmp)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math


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


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


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


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


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:
import pprint as pp

class Main():
    def exchange(self, n1, n2):
        tmp = self.A[n1]
        self.A[n1] = self.A[n2]
        self.A[n2] = tmp

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

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

    def maxHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        if l <= self.H and self.A[l] > self.A[i]:
            largest = l
        else :
            largest = i
        if r <= self.H and self.A[r] > self.A[largest]:
            largest = r
        if largest != i:
            self.exchange(i, largest)
            self.maxHeapify(largest) # 再帰的に呼び出し

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

    def main(self):
        self.H = int( input() )
        self.A = [0]
        inputData = [int(x) for x in input().split()]
        self.A.extend(inputData)
        self.buildMaxHeap()
        for i in range(1, self.H+1):
            print(" " + str(self.A[i]), end = "" )
        print()

if __name__ == '__main__':
    M = Main()
    M.main()

Submission status: Accepted

Solution code:
def maxheapify(a, i):
    l = 2*i
    r = 2*i + 1
    if l <= h and a[l] > a[i]:
        large = l
    else:
        large = i
    if r <= h and a[r] > a[large]:
        large = r
     
    if large != i:
        a[i], a[large] = a[large], a[i]
        maxheapify(a, large)
 
h = int(input())
n = int(h/2)
klist = list(map(int,input().split()))
klist.insert(0,0)
 
for i in range(n):
    j = n - i
    maxheapify(klist, j)
 
print("",*klist[1:])

Submission status: Accepted

Solution code:
#coding: utf-8

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)

H = int(input())
A = [0] + list(map(int,input().split()))
buildMaxHeap(A)
A.pop(0)
print(" " + " ".join([str(num) for num in A]))

Submission status: Accepted

Solution code:
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 if r<H and l<H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

H=INT()
# 1-indexedにしたいので先頭に番兵的なものを足す
A=['']+LIST()

def maxHeapify(A, i):
    l=i*2
    r=i*2+1
    if l<=H and A[l]>A[i]:
        mx=l
    else:
        mx=i
    if r<=H and A[r]>A[mx]:
        mx=r
    if mx!=i:
        A[i],A[mx]=A[mx],A[i]
        maxHeapify(A, mx)

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

print(*A)

Submission status: Accepted

Solution code:
def get_left_index(A, i):
    if len(A) > 2 * i:
        return 2 * i
    else:
        return None

def get_right_index(A, i):
    if len(A) > 2 * i + 1:
        return 2 * i + 1
    else:
        return None

def max_heapfy(A, i):
    left = get_left_index(A, i)
    right = get_right_index(A, i)
    largest = i
    if left and A[left] > A[i]:
        largest = left
    if right and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapfy(A, largest)

H = int(input())
A = [0]
for elem in map(int, input().split()):
    A.append(elem)


def build_max_heap(A):
    for i in range(H//2, 0, -1):
        max_heapfy(A, i)
build_max_heap(A)
print(' ', end='')        
print(*A[1:])

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:
# coding: utf-8
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)

H = int(raw_input())
A = map(int, [0]+raw_input().split())
buildMaxHeap(A)
print " " + " ".join(map(str,A[1:]))

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_B
# Maximum Heap
# Result:
import sys

def max_heapify(ary, nary, i):
    left = i * 2
    right = left + 1
    if left <= nary and ary[left] > ary[i]:
        largest = left
    else:
        largest = i
    if right <= nary and ary[right] > ary[largest]:
        largest = right
    if largest != i:
        tmp = ary[i]
        ary[i] = ary[largest]
        ary[largest] = tmp
        max_heapify(ary, nary, largest)

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

_nary = int(sys.stdin.readline())
_ary = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
assert _nary == len(_ary)
_ary.insert(0, -1)

build_max_heap(_ary, _nary)
_ary.pop(0)
str_ = ''
for x in _ary:
    str_ += ' %d' % (x)
print str_

Submission status: Accepted

Solution code:
#!/usr/bin/python3
def left(i):
    return i * 2

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

def maxHeapify(A, i):
    H = len(A) - 1
    l = left(i)
    r = right(i)

    child = {}
    child[i] = A[i] 
    if l <= H:
        child[l] = A[l]
    if r <= H:
        child[r] = A[r]
    largest = max(child.items(), key=lambda x:x[1])[0]

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

def buildMaxHeap(A):
    H = len(A) - 1
    for i in range(H//2, 0, -1):
        maxHeapify(A, i)
    print(' ' + ' '.join(list(map(str, A[1:]))))

# main
H = int(input())
A = list(map(int, input().split()))
B = [0]
B.extend(A)
buildMaxHeap(B)

Submission status: Accepted

Solution code:
def parent(n):
    return (n+1)/2-1

def left(n):
    return (n+1)*2-1

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

def max_heapify(A, i):
    l = left(i)
    r = right(i)
    largest = i
    if l < len(A) and A[largest] < A[l]:
        largest = l
    if r < len(A) and A[largest] < A[r]:
        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 reversed(range((len(A)-1)/2+1)):
        max_heapify(A,i)

H = int(raw_input())
A = map(int, raw_input().strip().split(' '))
build_max_heap(A)
print "",
print " ".join(map(str,A))

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)