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

Solution code:
import math

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

def left(i):
    return 2 * i

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

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


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

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

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

build_max_heap(heap, n)

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

Submission status: WA: Presentation Error

Solution code:


def  maxHeapify(i):
    l =2*i
    r = 2*i+1
    # print(A[i])
    largest =0
    if l <=H and A[l]> A[i]:
        largest = l
    else:
        largest = i

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

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



H = int(input())

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

A = [-1]+A

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

Astr = list(map(str,A))

# print(" ",end="")

print(*A[1:])

Submission status: WA: Presentation Error

Solution code:
global A

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

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

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

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

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

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

Submission status: WA: Presentation Error

Solution code:
global A

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

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

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

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

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

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

Submission status: WA: Presentation Error

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

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

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

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

Submission status: WA: Presentation Error

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

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

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

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

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

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

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

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


H = int(input())
L = list(map(int, input().split()))
heap = Heap(L)
heap.buildMaxHeap()
heap.heap.pop(0)
print(*heap.heap)

Submission status: WA: Presentation Error

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

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

    if left <= H and A[left] > A[i]:
        largest = left
    else: largest = i
    if right <= H and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest],A[i]
        maxHeapify(H,A,largest)

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

buildmaxHeap(H,A)

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

Submission status: WA: Presentation Error

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

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

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

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

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

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

Submission status: WA: Presentation Error

Solution code:
import sys

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

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

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

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

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

if __name__ == "__main__":
    main()

Submission status: WA: Presentation Error

Solution code:
import sys

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

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

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

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

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

if __name__ == "__main__":
    main()

Submission status: WA: Presentation Error

Solution code:
import heapq

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

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

for i in range(N):
    ans.append(a[i][1])
    
print(*ans)

Submission status: WA: Presentation Error

Solution code:
import heapq

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

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

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

Submission status: WA: Presentation Error

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

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

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

Submission status: WA: Presentation Error

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

Submission status: WA: Presentation Error

Solution code:
import heapq

for i in range(2):
    line = input()
queue = [(-1)*int(x) for x in line.split()]
heapq.heapify(queue)

queue = [(-1)*x for x in queue]
output = ''
for node in queue:
    output += (str(node)+' ')
print(output.strip())

Submission status: WA: Presentation Error

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


def maxheapify(a, i):
    l = i*2 + 1
    r = i*2 + 2

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

    if largest != i:
        memo = a[i]
        a[i] = a[largest]
        a[largest] = memo
        maxheapify(a, largest)

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

print(*a)

Submission status: WA: Presentation Error

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


def maxheapify(a, i):
    l = i*2 + 1
    r = i*2 + 2

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

    if largest != i:
        memo = a[i]
        a[i] = a[largest]
        a[largest] = memo
        maxheapify(a, largest)

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

print(" ", *a)

Submission status: WA: Presentation Error

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

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

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

Submission status: WA: Presentation Error

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

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)