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):
        self.heap = []
        self.length = 0

    def __str__(self):
        return " " + " ".join(str(n) for n in self.heap)

    def up_insert(self, key):
        self.heap.append(key)
        self._upheap()
        self.length += 1

    def down_insert(self, key):
        self.heap.append(key)
        self.length += 1
        for i in range(self.length // 2, -1, -1):
            self._downheap(i)

    def down_many_insert(self, key):
        self.heap.extend(key)
        self.length += len(key)
        for i in range(self.length // 2, -1, -1):
            self._downheap(i)


    def _upheap(self):
        index = self.length - 1
        while True:
            parent_index = (index - 1) // 2
            if parent_index < 0 or self.heap[parent_index] >= self.heap[index]:
                break
            self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
            index = parent_index

    def _downheap(self, index):
        while True:
            child_index_left, child_index_right = index * 2 + 1, index * 2 + 2
            # print(index, child_index_left, child_index_right)
            if child_index_left >= self.length:
                break
            elif (child_index_right >= self.length or self.heap[child_index_left] > self.heap[child_index_right]) and self.heap[index] < self.heap[child_index_left]:
                self.heap[index], self.heap[child_index_left] = self.heap[child_index_left], self.heap[index]
                index = child_index_left
            elif (child_index_right < self.length and self.heap[child_index_left] < self.heap[child_index_right]) and self.heap[index] < self.heap[child_index_right]:
                self.heap[index], self.heap[child_index_right] = self.heap[child_index_right], self.heap[index]
                index = child_index_right
            else:
                break



a = MaxHeap()
length = int(input())
t = [int(n) for n in input().split(" ")]
a.down_many_insert(t)
print(a)

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 maxHeapify(A, i):
    l = left(i)
    r = right(i)

    if l <= n and A[l] > A[i]:
        largest = l
    else:
        largest = i

    if r <=n and A[r] > A[largest]:
        largest = r

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

def buildMaxHeap(A):
    for i in range(n//2, 0, -1):
        maxHeapify(A, i)
    
if __name__ == "__main__":
    n = int(input())
    A = [None]
    A.extend(list(map(int, input().split())))
    buildMaxHeap(A)
    print(" " + ' '.join(map(str, A[1:])))

Submission status: Accepted

Solution code:
def max_heapify(nodes, idx):
    left_idx = idx * 2
    right_idx = idx * 2 + 1

    max_idx = idx

    if left_idx <= len(nodes) and nodes[left_idx-1] > nodes[max_idx-1]:
        max_idx = left_idx
    if right_idx <= len(nodes) and nodes[right_idx-1] > nodes[max_idx-1]:
        max_idx = right_idx

    if max_idx != idx:
        tmp = nodes[idx-1]
        nodes[idx-1] = nodes[max_idx-1]
        nodes[max_idx-1] = tmp
        max_heapify(nodes, max_idx)
    return


def build_maxheap(nodes):
    for i in range(1, len(nodes)//2 + 1)[::-1]:
        max_heapify(nodes, i)
    return


def main():
    num_node = int(input())
    nodes = [int(x) for x in input().split()]
    build_maxheap(nodes)
    print(" " + " ".join(map(str, nodes)))
    return


main()

Submission status: Accepted

Solution code:
import sys

H = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().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, -1):
        maxHeapify(A, i)

buildMaxHeap(A)
print('',' '.join(map(str,A)))

Submission status: Accepted

Solution code:
#heapは1オリジンであり、index0にはダミーが入っているところに注意


def max_heapify(heap,i):#heapのi番目の要素とその子供について,heap条件を整える
    l=2*i
    r=2*i+1
    largest=i

    if(l < len(heap) and heap[i] < heap[l]):
        largest=l
    if(r < len(heap) and heap[largest] < heap[r]):
        largest=r
    if(i!=largest):
        heap[i],heap[largest]=heap[largest],heap[i]
        max_heapify(heap,largest)






n=int(input())
heap=list(map(int,input().split()))
heap.insert(0,-1)

for i in range(n//2 +1):
    max_heapify(heap,n//2 +1 -i)

for i in range(1,n+1):
    print(f" {heap[i]}",end="")
print()

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
def heapify(i):
    l = 2*i+1; r = 2*i+2
    left = l < N and A[i] < A[l]
    right = r < N and A[i] < A[r]
    if left and right:
        if A[l] < A[r]:
            left = 0
        else:
            right = 0
    if left:
        A[i], A[l] = A[l], A[i]
        heapify(l)
    elif right:
        A[i], A[r] = A[r], A[i]
        heapify(r)


for i in range(N-1, -1, -1):
    heapify(i)
print("",*A)

Submission status: Accepted

Solution code:
import math

def max_heapify(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]
        max_heapify(A, largest)
        
        
def build_max_heap(A):
    for i in range(math.floor(len(A)-1), 0, -1):
        max_heapify(A, i)
        
H = int(input())
A = [None] + list(map(int, input().split()))
build_max_heap(A)

for a in A[1:]:
    print(f" {a}", end="")
print("")

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

  build_maxheap(A)
  A = A[1:]
  print(' {0}'.format(' '.join(map(str, A))))

Submission status: Accepted

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


def swap(A, i, j):
    tmp = A[i]
    A[i] = A[j]
    A[j] = tmp


def heap_size(A):
    return len(A) - 1


def parent_node(k):
    return k // 2


def left_node(k):
    return 2 * k


def right_node(k):
    return 2 * k + 1


def max_heapify(A, i):
    l = left_node(i)
    r = right_node(i)

    if l <= heap_size(A) and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= heap_size(A) and A[r] > A[largest]:
        largest = r

    if largest != i:
        swap(A, i, largest)
        max_heapify(A, largest)


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


def print_heap(A):
    for i in range(1, heap_size(A) + 1):
        print(" {}".format(A[i]), end="")
    print()


def main():
    _ = int(input())
    A = [None] + [int(x) for x in input().split()]

    build_max_heap(A)
    print_heap(A)


main()

Submission status: Accepted

Solution code:
def max_heapify(A, n, i):
    l = 2 * i
    r = 2 * i + 1

    if l < n+1 and A[l] > A[i]:
        largest = l
    else:
        largest = i

    if r < n+1 and A[r] > A[largest]:
        largest = r
        
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, n, largest)

n = int(input())
A = [None] + [int(i) for i in input().split()]
for i in range(int(n/2), 0, -1):
    max_heapify(A, n, i)
print(" ", end="")
print(*A[1:], sep=" ")

Submission status: Accepted

Solution code:
def build_max_heap(n,a):
	for i in range(int(n/2),0,-1):
		max_heap(n,a,i)

def max_heap(n,a,i):
	l = i * 2
	r = i * 2 + 1
	larg = i
	if l <= n and a[i-1] < a[l-1]:
		larg = l
	if r <= n and a[larg-1] < a[r-1]:
		larg = r
	if larg != i:
		tmp = a[larg-1]
		a[larg-1] = a[i-1]
		a[i-1] = tmp
		max_heap(n,a,larg)		

n = int(input())
a = list(map(int,input().split()))
build_max_heap(n,a)
for i in range(n):
	print(' ' + str(a[i]), end='')
print()

Submission status: Accepted

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

def buildMaxHeap(A, H):
    for i in range(H//2,0,-1):
        maxHeapify(A, i)
        
H = int(input())
A = [int(i) for i in input().split()]
A = [0] + A
buildMaxHeap(A, H)
tmp = ""
for i in A[1:]:
    tmp+= " " + str(i)
print(tmp)

Submission status: Accepted

Solution code:
def maxHeapfy(a, h, 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]
        maxHeapfy(a, h, largest)


h = int(input())
a = [-1]
a.extend([int(v) for v in input().split()])

for i in range(h//2, 0, -1):
    maxHeapfy(a, h, i)

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

Submission status: Accepted

Solution code:
# Heaps - Complete Binary Tree
from math import floor

def parent(i):
    p_id = floor(i/2)
    if p_id > 0: return p_id
    else: return 0

def left(H,i):
    l_id = 2 * i
    if 0 < l_id < H: return l_id
    else: return 0

def right(H,i):
    r_id = 2 * i + 1
    if 0 < r_id < H: return r_id
    else: return 0

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

def max_heapify(A,i):
    H = len(A)
    l = left(H,i)
    r = right(H,i)
    largest = 0
    if 1 <= H and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= H and A[r] > A[largest]:
        largest = r
    if not largest == i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

H = int(input())
heap = [-2000000001]*(H+1)
for i,k in enumerate(input().split()):
    heap[i+1] = int(k)

build_max_heap(heap)

for i,h in enumerate(heap):
    if i == 0: continue
    print(' {0}'.format(h), end='')
print()

Submission status: Runtime Error

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 &&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: Runtime Error

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 && 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: Runtime Error

Solution code:
# coding: utf-8
def maxHeapify(A, i):
    l = A[2*(i+1)-1]
    r = A[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:???# 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, raw_input().split())
buildMaxHeap(A)
print A

Submission status: Runtime Error

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: Runtime Error

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
    left = heap[left_index] if left_index < len(heap) else -1
    right = heap[right_index] if right_index < len(heap) else -1
    largest_index = heap.index(max([left, right, heap[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: Runtime Error

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] else i
        largest = right if heap[right] > heap[largest]
        if largest != i:
            heap[i], heap[largest] = heap[largest], heap[i]
        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: Runtime Error

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

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: Runtime Error

Solution code:
def maxHeapify(heap, i):
    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: Runtime Error

Solution code:
def maxHeapify(heap, i):
    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)
'''
out = ''
for key in heap:
    out += (' {}'.format(str(key)))
print(out)
'''

Submission status: Runtime Error

Solution code:
def maxHeapify(heap, i):
    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: Runtime Error

Solution code:
def maxHeapify(heap, i):
    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)
'''
out = ''
for key in heap:
    out += (' {}'.format(str(key)))
print(out)
'''

Submission status: Runtime Error

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

def maxHeapify(heap, i):
    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)

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

Submission status: Runtime Error

Solution code:
input()
A=[0]+list(map(int,input().split()))
H=len(A)
def h(i):
 l=2*i;r,g=l+1,[i,l][A[i]<A[l]and l<H]
 if A[g]<A[r]and r<H:g=r
 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: Runtime Error

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][2*i<H],A[i,2*i+1][2*i+1<H]))
 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: Runtime Error

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 and A[g]<A[r]:g=l if A[i]<A[l]else r
 else:if l<H and A[i]<A[l]:g=l
 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: Runtime Error

Solution code:
import numpy as np
import sys

def maxHeapify(array,i):
    l = 2 * i
    r = 2 * i + 1
    largest = i
    #print("i,array[i] ==: " + str(i) + ", " + str(array[i]))
    #print(array)

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

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

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

def buildMaxHeap(array):
    for i in range( int((len(array)-1) / 2),0,-1):
        maxHeapify(array,i)
    return array

if __name__ == "__main__":
    h = int(input())
    array = [1]
    array[0] = 0
    array.extend(list(map(int,input().split())))
    #print("original == :" + str(array))
    maxheap = buildMaxHeap(array)
    maxheap.pop(0)
    print(maxheap)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

def maxHeapify(array,i):
    l = 2 * i
    r = 2 * i + 1
    largest = i
    #print("i,array[i] ==: " + str(i) + ", " + str(array[i]))
    #print(array)

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

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

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

def buildMaxHeap(array):
    for i in range( int((len(array)-1) / 2),0,-1):
        maxHeapify(array,i)
    return array

if __name__ == "__main__":
    h = int(input())
    array = [1]
    array[0] = 0
    array.extend(list(map(int,input().split())))
    #print("original == :" + str(array))
    maxheap = buildMaxHeap(array)
    maxheap.pop(0)
    print('',*maxheap)

Submission status: WA: Presentation Error

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: WA: Presentation Error

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

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

Submission status: WA: Presentation Error

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: WA: Presentation Error

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=[0]+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[1:])

Submission status: WA: Presentation Error

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: WA: Presentation Error

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)
for x in _ary:
    print ' %d' % (x),
print

Submission status: WA: Presentation Error

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: WA: Presentation Error

Solution code:
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: WA: Presentation Error

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: WA: Presentation Error

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 " ".join(map(str,A))

Submission status: WA: Presentation Error

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 ' '.join(map(str,a))

Submission status: WA: Presentation Error

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