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 Node():
    def __init__(self, id, key, parent, left, right):
        self.id = id
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
    def show(self):
        print 'node %d: key = %d,' % (self.id, self.key),
        if self.parent:
            print 'parent key = %d,' % self.parent, 
        if self.left:
            print 'left key = %d,' % self.left,
        if self.right:
            print 'right key = %d,' % self.right,
        print ''

def calcParent(key):
    if key == 1:
        return None
    else:
        return data[int(key/2) - 1]

def calcLeft(key, flag=0):
    if flag == 1:
        return 2 * key
    if 2 * key < n + 1:
        return data[2 * key - 1]
    return None

def calcRight(key, flag=0):
    if flag == 1:
        return 2 * key + 1
    if 2 * key < n:
        return data[2 * key]
    return None

def maxHeapify(T, i):
    val_i, val_l, val_r = T[i].key, None, None
    if T[i].left:
        val_l = T[i*2].key
    if T[i].right:
        val_r = T[i*2+1].key
    if val_l and val_l > val_i:
        largest = val_l
    else:
        largest = val_i
    if val_r and val_r > largest:
        largest = val_r
    if largest != val_i:
        T[i].key = largest
        if T[i].parent:
            if T[int(i/2)].left == val_i:
                T[int(i/2)].left = largest
            else:
                T[int(i/2)].right = largest
        if largest == val_l:
            T[i*2].key = val_i
            T[i*2].parent = largest
            T[i].left = val_i
            T = maxHeapify(T, i*2)
        else:
            T[i*2+1].key = val_i
            T[i*2+1].parent = largest
            T[i].right = val_i
            T = maxHeapify(T, i*2+1)
    return T
        
n = int(raw_input())
data = map(int, raw_input().split())
T = {}
for i in range(n):
    this_id = i + 1
    T[this_id] = Node(i+1, data[i], calcParent(this_id), calcLeft(this_id), calcRight(this_id))
for i in range(int(n/2), 0, -1):
    T = maxHeapify(T, i)
    
print '',
for i in T.keys():
    print  T[i].key,

Submission status: Accepted

Solution code:
H = int(input())
A = list(map(int, input().split()))

def MaxHeapify(a, i):
    li, ri = 2*i+1, 2*i+2
    if li < H and a[li] > a[i]:
        largest = li
    else:
        largest  = i
        
    if ri < H and a[ri] > a[largest]:
        largest = ri
        
    if a[largest] > a[i]:
        a[i], a[largest] = a[largest], a[i]
        MaxHeapify(a, largest)

def BuildMaxHeap(a):
    for i in range(H//2, -1, -1):
        MaxHeapify(a, i)
        
BuildMaxHeap(A)

print(' ', end='')
print(*A)

Submission status: Accepted

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

A = [int(i) for i in input().split()]
buildMaxHeap(A)
print(' ' + ' '.join(map(str,A)))

Submission status: Accepted

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

h = int(input())
n = int(0.5*h)
key = list(map(int,input().split()))
key.insert(0,0)

for i in range(n):
    j = n - i
    maxHeapify(key, j)

print("",*key[1:])

Submission status: Accepted

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


def max_Heapify(tree, n, i):
    left = (i + 1) * 2 - 1
    right = left + 1

    if left < n and tree[left] > tree[i]:
        largest = left
    else:
        largest = i

    if right < n and tree[right] > tree[largest]:
        largest = right

    if largest != i:
        tree[i], tree[largest] = tree[largest], tree[i]
        max_Heapify(tree, n, largest)


def BuildMaxHeap(tree, n):
    for i in range(n // 2 - 1, -1, -1):
        max_Heapify(tree, n, i)


if __name__ == "__main__":
    n = int(input())
    tree = [int(n) for n in input().split()]
    BuildMaxHeap(tree, n)
    print(" " + " ".join([str(n) for n in tree]))

Submission status: Accepted

Solution code:
def maxHeapify(A,i,H):
    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:
        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: Accepted

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

def parent(i):
    return i // 2

def left(i):
    return 2*i

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

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

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

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


if __name__ == '__main__':

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

    buildMaxHeap(A)

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

Submission status: Accepted

Solution code:
H = int(input())
L = list(map(int, input().split()))
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < H and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < H and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest)
def buildMaxHeap(A):
    for i in range(H // 2, -1, -1):
        maxHeapify(A, i)
buildMaxHeap(L)
print("", *L)

Submission status: Accepted

Solution code:
H = int(input())
L = list(map(int, input().split()))
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < H and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < H and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest)
def buildMaxHeap(A):
    for i in range(H // 2, -1, -1):
        maxHeapify(A, i)
buildMaxHeap(L)
print("", " ".join(map(str, L)))

Submission status: Accepted

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][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]: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)
a=''
for s in A[1:]:a+=f' {s}'
print(a)

Submission status: Accepted

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][l<H and A[i]<A[l]]
 if r<H and A[g]<A[r]: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: Accepted

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

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

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

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

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

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

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 l<H and A[g]<A[l]:g=l
 if r<H and A[g]<A[r]: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: 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:
  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:
H=int(input())+1
A=[0]+list(map(int,input().split()))
def s(x,y):A[x],A[y]=A[y],A[x];h(y)
def h(i):
 l=2*i;r=l+1
 if r<H:
  if A[i]<A[l]:
   if A[l]<A[r]:s(i,r)
   else:s(i,l)
  elif A[i]<A[r]:s(i,r)
 elif l<H and A[i]<A[l]:s(i,l)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))

Submission status: Accepted

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)

for i in reversed(range(n)):
    maxheapify(a, i)

print("", *a)

Submission status: Accepted

Solution code:
class Heap:
    def __init__(self, a = []):
        self.h = a
        self.n = len(a)
# 接点の添字iが与えられた時、その親、左の子、右の子の添字はそれぞれi//2, 2i, 2i+1
# ヒープの添字は1-indexed
    def parent(self, i): # 添字をもらって、その親の添字
        return i // 2
    def left(self, i):
        return i * 2
    def right(self, i):
        return i * 2 + 1
    def max_heapify(self, i):
        l = self.left(i)
        r = self.right(i)
# 左の子、自分、右の子で値が最大のノードを選ぶ
        if l <= self.n and self.h[l-1] > self.h[i-1]:
            largest = l
        else:
            largest = i
        if r <= self.n and self.h[r-1] > self.h[largest-1]:
            largest = r
        if largest != i: # 子の方が値が大きい場合
            self.h[i-1], self.h[largest-1] = self.h[largest-1], self.h[i-1]
            self.max_heapify(largest)
    def build_max_heap(self):
        for i in range((self.n // 2), 0, -1):
            self.max_heapify(i)

heap = Heap()
heap.n = int(input())
heap.h = list(map(int, input().split()))
heap.build_max_heap()
print("", *heap.h)

Submission status: Accepted

Solution code:
class Heap:
    def __init__(self, nodes):
        self._nodes = nodes
        self.size = len(nodes)

    def max_heapify(self):
        def _max_heapify(i):
            left = (i+1) * 2 - 1
            right = (i+1) * 2
            if left < self.size and self._nodes[left] > self._nodes[i]:
                largest = left
            else:
                largest = i

            if right < self.size and self._nodes[right] > self._nodes[largest]:
                largest = right

            if largest > i:
                self._nodes[i], self._nodes[largest] = \
                        self._nodes[largest], self._nodes[i]
                _max_heapify(largest)

        for i in reversed(range(self.size//2)):
            _max_heapify(i)

    def __iter__(self):
        self.cur = 0
        return self

    def __next__(self):
        if self.cur >= self.size:
            raise StopIteration
        node = self._nodes[self.cur]
        self.cur += 1

        return node

    @classmethod
    def create(cls, li):
        heap = cls(li[:])
        heap.max_heapify()
        return heap


def run():
    _ = int(input())

    nodes = [int(i) for i in input().split()]
    heap = Heap.create(nodes)

    s = ''
    for node in heap:
        s += ' {}'.format(node)

    print(s)


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
n = int(input())
a = [0] + list(map(int, input().split()))
def max_heapify(a, i):
    global n
    l = 2 * i
    r = 2 * i + 1
    largest = l if l <= n and a[l] > a[i] else i
    if r <= n and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[largest], a[i] = a[i], a[largest]
        max_heapify(a, largest)

for i in range(int(n / 2), 0, -1):
    max_heapify(a, i)
    
print(" " + " ".join(map(str, a[1:])))

Submission status: Accepted

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

def max_heapify(i):
    l = (i+1)*2-1
    r = (i+1)*2
    largest = i
    if l < n and H[l] > H[i]:
        largest = l
    else:
        largest = i
    if r < n and H[r] > H[largest]:
        largest = r

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

def print_elements(lst):
    for ele in lst:
        print(' {}'.format(ele), end='')
    print('')

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

print_elements(H)

Submission status: Accepted

Solution code:
from collections import deque

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

    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 = 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())
H = list(map(int, input().split(' ')))

def max_heapify(i):
    l = (i+1)*2-1
    r = (i+1)*2
    largest = i
    if l < n and H[l] > H[i]:
        largest = l
    else:
        largest = i
    if r < n and H[r] > H[largest]:
        largest = r

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

def print_elements(lst):
    for ele in lst:
        print(' {}'.format(ele), end='')
    print('')

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

print_elements(H)

Submission status: Accepted

Solution code:
def maxHeapify(i, node_list):
    n = len(node_list)
    if 2*i+1 < n and node_list[2*i+1] > node_list[i]:
        i_largest = 2*i+1
        # node_list[i], node_list[2*i+1] = node_list[2*i+1], node_list[i]
    else:
        i_largest = i
    if 2*i+2 < n and node_list[2*i+2] > node_list[i_largest]:
        i_largest = 2*i+2
        # node_list[i], node_list[2*i+2] = node_list[2*i+2], node_list[i]

    if i_largest != i:
        node_list[i], node_list[i_largest] = node_list[i_largest], node_list[i]
        maxHeapify(i_largest, node_list)




n = int(input())
node_list = [int(i) for i in input().split()]
for i in range(n//2, -1, -1):
    maxHeapify(i, node_list)
print(' ' + ' '.join([str(node) for node in node_list]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H = int(input())
ary = [int(_) for _ in input().split()]


def max_heapify(ary, i):
    l = 2 * i
    r = 2 * i + 1
    if l <= H and ary[l - 1] > ary[i - 1]:
        largest = l
    else:
        largest = i
    if r <= H and ary[r - 1] > ary[largest - 1]:
        largest = r

    if largest != i:
        ary[i - 1], ary[largest - 1] = ary[largest - 1], ary[i - 1]
        max_heapify(ary, largest)


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


build_max_heap(ary)
print(' ', end='')
print(*ary)

Submission status: Accepted

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]),end = '')
print()

Submission status: Accepted

Solution code:
def max_heapify(a, i):
    h = len(a)
    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:
        tmp = a[i - 1]
        a[i - 1] = a[largest - 1]
        a[largest - 1] = tmp
        max_heapify(a, largest)


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


def print_list_split_whitespace(a):
    s = ""
    for x in a:
        s += " " + str(x)
    print(s)


h = int(input())
heap = [int(x) for x in input().split()]

build_max_heap(heap)

print_list_split_whitespace(heap)

Submission status: Accepted

Solution code:
#coding:utf-8
H = int(input())
A = list(map(int,input().split()))

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

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

buildMaxHeap(A)
A = " " + " ".join([str(num) for num in A])
print(A)

Submission status: Accepted

Solution code:
import sys

def parent(i, n):
    tmp = i/2
    if tmp <=0 or tmp>=n: return None
    else: return tmp

def left(i, n):
    tmp = 2*i
    if tmp>=n: return None
    else: return tmp
    
def right(i, n):
    tmp = 2*i+1
    if tmp>=n: return None
    else: return tmp

def maxheapify(A, i):
    n = len(A)
    f = [0,0,0]
    f[0] = A[i]

    l=left(i, n)
    if l == None:
        f[1]=None
    else:
        f[1]=A[l]
    
    r=right(i,n)
    if r == None:
        f[2]=None
    else:
        f[2]=A[r]
        
    tmp = f.index(max(f))
    if tmp == 1:
        tmp=A[i]
        A[i]=A[l]
        A[l]=tmp
        maxheapify(A, l)
    elif tmp == 2:
        tmp=A[i]
        A[i]=A[r]
        A[r]=tmp
        maxheapify(A, r)

def buildmaxheap(A):
    for i in range(1,len(A))[::-1]:
        maxheapify(A,i)
        
n = int(input())
x = map(int, [0] + raw_input().split()) 
buildmaxheap(x)
print " "+" ".join(map(str, x[1:]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import division, print_function
from sys import stdin


def max_heapify(a, i, heap_size):
    L = 2*i
    R = 2*i + 1
    if L <= heap_size and a[L] > a[i]:
        largest = L
    else:
        largest = i
    if R <= heap_size and a[R] > a[largest]:
        largest = R
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest, heap_size)


def build_max_heap(a, heap_size):
    for i in range(heap_size//2, 0, -1):
        max_heapify(a, i, heap_size)


heap_size = int(stdin.readline())
assert heap_size <= 500000
data = [0]
data.extend(int(s) for s in stdin.readline().split())
build_max_heap(data, heap_size)
print('', *data[1:])

Submission status: Accepted

Solution code:
import heapq
N = input()
H = [-x for x in map(int, input().split())]

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

Submission status: Accepted

Solution code:
def heapify(A, i):
    right_i = (i+1)*2-1
    left_i = (i+1)*2
    if right_i  > len(A)-1:
        return
    if left_i > len(A)-1:
        if A[right_i] > A[i] :
            A[right_i], A[i] = A[i], A[right_i ]
        return
    if A[i] < A[right_i] and A[left_i] < A[right_i ]:
        A[right_i ], A[i] = A[i], A[right_i ]     
        heapify(A, right_i )
    if A[i] < A[left_i] and A[right_i] < A[left_i]:
        A[left_i ], A[i] = A[i], A[left_i ]     
        heapify(A, left_i)

def build_heap(A):
    for i in reversed(range(len(A)//2)):
        heapify(A, i)

input()    
input_list = list(map(int, input().split()))
build_heap(input_list)

output = ""
for i in input_list:
    output += " " + str(i)
print(output)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/9/ALDS1_9_B

def max_heapify(A, i):
    left = 2 * i + 1
    right = 2 * i + 2
    if left < len(A) and A[left] > A[i]:
        largest = left
    else:
        largest = i
    if right < len(A) and A[right] > A[largest]:
        largest = right

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


def main():
    h = int(input())
    A = [int(i) for i in input().split()]
    for i in range(0, h // 2)[::-1]:
        max_heapify(A, i)

    print(" " + " ".join([str(i) for i in A]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush, heappushpop

N = int(input())
H = [-x for x in map(int,input().split())]

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

Submission status: Accepted

Solution code:

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

def buildMaxHeap(a):
    i = H//2 
    while i>=1:
        maxHeapify(i)
        i -= 1
    
    

H = int(input())
a = list(map(int,input().split()))
a.insert(0,0)
buildMaxHeap(a)
del a[0]
print(' ',end = "")
print(*a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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 <= H and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= H and A[r] > A[largest]:
        largest = r
    
    if largest != i:
        A[i], A[largest] = A[largest], A[i] # pythonはこれで要素の入れ替えが可能
        maxHeapify(A, largest)

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

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

buildMaxHeap(A, H)

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

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')

parent = lambda i: math.floor(i / 2)
left = lambda i: 2 * i
right = lambda i: 2 * i + 1


def max_heapify(A, H, i):
    l = left(i) + 1
    r = right(i) + 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, H, largest)


def build_max_heap(A, H):
    for i in reversed(range(H // 2)):
        max_heapify(A, H, i)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H = ii()
    heap = il()
    build_max_heap(heap, H)
    print('', *heap)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class CompleteBinaryTree:
    def __init__(self, nodes):
        self.size = len(nodes)
        self.nodes = [None] + nodes
        
    
    def print_nodes(self):
        for i in range(1,self.size + 1):
            if i == 1:
                print('node {0}: key = {1}, left key = {2}, right key = {3}, '.format(i, self.nodes[i], self.nodes[2*i], self.nodes[2*i+1]))
            elif 2*i < self.size:
                print('node {0}: key = {1}, parent key = {2}, left key = {3}, right key = {4}, '.format(i, self.nodes[i], self.nodes[i//2], self.nodes[2*i], self.nodes[2*i+1]))
            elif 2*i == self.size:             
                print('node {0}: key = {1}, parent key = {2}, left key = {3}, '.format(i, self.nodes[i], self.nodes[i//2], self.nodes[2*i]))
            else:
                print('node {0}: key = {1}, parent key = {2}, '.format(i, self.nodes[i], self.nodes[i//2]))


    def _find_left(self, i):
        if 2*i <= self.size:
            return self.nodes[2*i]
        else:
            return -9999999999


    def _find_right(self, i):
        if 2*i+1 <= self.size:
            return self.nodes[2*i+1]
        else:
            return -9999999999


    def maxHeapify(self, i):
        n, l, r = self.nodes[i], self._find_left(i), self._find_right(i)
        if max(n, l, r) == l:
            self.nodes[i], self.nodes[2*i] = self.nodes[2*i], self.nodes[i]
            self.maxHeapify(2*i)
        elif max(n, l, r) == r:
            self.nodes[i], self.nodes[2*i+1] = self.nodes[2*i+1], self.nodes[i]
            self.maxHeapify(2*i+1)
            
    
    def buildMaxHeap(self):
        for i in range(self.size//2,0,-1):
            self.maxHeapify(i)


if __name__ == '__main__':
    n = int(input())
    nodes = list(map(int, input().rstrip().split()))
    cbt = CompleteBinaryTree(nodes)
    cbt.buildMaxHeap()
    print(' ' + ' '.join(map(str,cbt.nodes[1:])))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

def maxHeapify(A, i):
    c = i
    l = 2*(i+1)-1 if 2*(i+1)<=H  else H+1
    r = 2*(i+1)+1-1 if 2*(i+1)+1<=H else H+1 

    # select maximum node from left, me, right
    if (l<=H) and (A[l]>A[c]):
        largest = l
    else:
        largest = c
    if (r<=H) and (A[r]>A[largest]):
        largest = r
        
    if largest!=c:
        A[c],A[largest] = A[largest],A[c]
        if 2*(largest+1)<=H:
            maxHeapify(A, largest)
    return A

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

Submission status: Accepted

Solution code:
from heapq import *
n = int(input())
H = [-x for x in map(int,input().split())]
heapify(H)
print(""," ".join([str(-x) for x in H]))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

def maximum_heap(nums,i):
    left_index=2*(i+1)-1
    right_index=2*(i+1)
    if left_index<n and nums[left_index]>nums[i]:
        largest=left_index
    else:
        largest=i
    if right_index<n and nums[right_index]>nums[largest]:
        largest=right_index
    
    if largest!=i:
        nums[largest],nums[i]=nums[i],nums[largest]
        maximum_heap(nums,largest)

for i in range(int(n/2)-1,-1,-1):
    maximum_heap(nums,i)

print(" ",end="")
for i in range(n):
    if i!=n-1:
        print(nums[i],end=" ")
    else:
        print(nums[i])