#!/usr/bin/env python3


class Heap:
    def __init__(self, cap):
        self.heapSize = 0
        
        #self.heapArray[self.indexArray[index]] = index
        #self.indexArray[self.heapArray[position]] = position
        self.heapArray = [0] * cap
        self.indexArray = [0] * cap
        self.keyArray = [0] * cap
    
    def __str__(self):
        return str(self.heapSize)+"\n"+str(self.heapArray)+"\n"+str(self.indexArray)+"\n"+str(self.keyArray)
        
    def key(self, position):
        return self.keyArray[self.heapArray[position]]
    
    def add_elm(self, index, key):
        position = self.heapSize
        
        self.heapArray[position] = index
        self.indexArray[index] = position
        self.keyArray[index] = key
        
        self.heapSize = self.heapSize + 1
        
        self.update_pos(position)
        
        
    def del_min(self):
        self.switch(self.root(), self.last())
        self.heapSize = self.heapSize - 1
        self.update_pos(self.root())
        
    def del_elm(self, index):
        position = self.indexArray[index]
        self.switch(position, self.last())
        self.heapSize = self.heapSize - 1
        self.update_pos(position)
        
    def update_elm(self, index, key):
        position = self.indexArray[index]
        if self.keyArray[index] > key:
            self.keyArray[index] = key
        self.update_pos(position)
        
    def output_min(self):
        return self.heapArray[self.root()], self.key(self.root())
        
    def update_pos(self, position):
        while (not self.is_root(position)) and self.key(self.parent(position)) > self.key(position):
            self.switch(position, self.parent(position))
            position = self.parent(position)
        
        while (not self.is_leaf(position)) and self.key(position) > self.key(self.lesser_child(position)):
            newPosition = self.lesser_child(position)
            self.switch(position, self.lesser_child(position))
            position = newPosition
        
    def switch(self, position1, position2):
        self.heapArray[position1], self.heapArray[position2] = self.heapArray[position2], self.heapArray[position1]
        self.indexArray[self.heapArray[position1]] = position1
        self.indexArray[self.heapArray[position2]] = position2
        
    def root(self):
        return 0
    
    def last(self):
        return self.heapSize - 1
    
    def parent(self, position):
        return (position - 1) // 2
    
    def left_child(self, position):
        return position*2 + 1
        
    def right_child(self, position):
        return self.left_child(position) + 1
    
    def lesser_child(self, position):
        if self.left_child(position) == self.last():
            return self.left_child(position)
        if self.key(self.left_child(position)) < self.key(self.right_child(position)):
            return self.left_child(position)
        return self.right_child(position)
    
    def is_root(self, position):
        return position == self.root()
    
    def is_leaf(self, position):
        return self.left_child(position) > self.last()