Problem:
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 ≠ 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.

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

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

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

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

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

Solution (Python):


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

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

Solution (Python):


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

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)

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

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

Solution (Python):

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

Solution (Python):



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_

Solution (Python):

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


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

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

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

Solution (Python):
class MaxHeap():
    def __init__(self, a, h):
        self.a = a
        self.h = h
    def parent(self, i):
        return i//2
        
    def left(self, i):
        return 2 * i

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

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

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

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

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

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


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

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

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

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


H = int(input())

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

buildMaxHeap(A, H)

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

Solution (Python):


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

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

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

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

def max_heapify(A, i):
	l = i * 2 
	r = i * 2 + 1
	largest = i
	if l <= H:
		if A[l] > A[largest]:
			largest = l
	if r <= H:
		if A[r] > A[largest]:
			largest = r
	if largest != i:
		A[i], A[largest] = A[largest], A[i]
		max_heapify(A, largest)

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

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

Solution (Python):
import sys

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

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

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

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

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

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

Solution (Python):


def max_heapify(heap, i):
    l = (i+1)*2 - 1
    r = (i+1)*2

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

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

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

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

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

    def size(self):
        return self.index_max

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

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

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

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

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

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

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

        if (l_idx is not None) and (self.val_at(l_idx) > self.val_at(i)):
            swap_target = l_idx
            
            if r_idx is not None and self.val_at(r_idx) > self.val_at(l_idx):
                swap_target = r_idx
        elif r_idx is not None and self.val_at(r_idx) > self.val_at(i):
            swap_target = r_idx

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

    def build_max_heap(self):
        for i in reversed(range(1, self.size()//2+1)):
            
            
            self.max_heapify(i)

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


if __name__ == "__main__":
    H = int(input())   
    vals_str = input()   
    vals = list(map(int, vals_str.split(' ')))
    mh = max_heap(vals)
    mh.build_max_heap()
    print(mh.show())

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

def maxHeapify(A,i):
    l = left(i)
    r = right(i)
    largest = i
    if get_item(A,l) > A[largest]: largest = l
    if get_item(A,r) > A[largest]: largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i] 
        maxHeapify(A, largest)


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


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

Solution (Python):
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 
        heapify(a,j)

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

Solution (Python):


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

Solution (Python):
import math

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

def left(i):
    return 2 * i

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

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


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

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

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

build_max_heap(heap, n)

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

Solution (Python):
import math

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

def left(i):
    return 2 * i

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

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


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

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

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

build_max_heap(heap, n)

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

Solution (Python):
import math

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

def left(i):
    return 2 * i

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

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


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

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

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

build_max_heap(heap, n)

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

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

Solution (Python):


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



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

Solution (Python):


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



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

Solution (Python):



import sys


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

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

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

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

    return None


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

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

Solution (Python):



import sys


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

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

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

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

    return None


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

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

Solution (Python):



import sys


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

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

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

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

    return None


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

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

Solution (Python):



import sys


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

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

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

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

    return None


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

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

Solution (Python):

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

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

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

    
    build_maxheap(A)
    A = A[1:]  

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

Solution (Python):



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

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

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

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

Solution (Python):



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

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

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

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

Solution (Python):



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

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

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

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

Solution (Python):



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

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

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

Solution (Python):
import sys

def maxHeapify(H, A, i):
    left = 2 * i
    right = 2*i + 1

    if left <= H and A[left] > A[i]:
        largest = left
    else:
        largest = i
    if right <= H and A[right] > A[largest]:
        largest = right

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

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

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

buildMaxHeap(H, A)

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

Solution (Python):


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)