class Heap:
        def __init__(self):
            self.heap = []
            self.index = {}
            self.value = {}
            
        def __str__(self):
            ret = "["
            for i, key in enumerate(self.heap):
                ret += str(key)
                if i < len(self.heap) - 1:
                    ret += ", "
            ret += "]\n["
            for i, key in enumerate(self.heap):
                ret += str(self.value[key])
                if i < len(self.heap) - 1:
                    ret += ", "
            ret += "]"
            return ret
            
        def hasParent(self, pos):
            return pos > 0
            
        def parentPos(self, pos):
            return (pos-1)//2
            
        def parentVal(self, pos):
            return self.value[self.heap[self.parentPos(pos)]]
            
        def currentVal(self, pos):
            return self.value[self.heap[pos]]
            
        def hasTwoChilds(self, pos):
            return len(self.heap) > self.rightChildPos(pos)
            
        def hasOneChild(self, pos):
            return len(self.heap) == self.rightChildPos(pos)
            
        def leftChildPos(self, pos):
            return 2*pos+1
            
        def leftChildVal(self, pos):
            return self.value[self.heap[self.leftChildPos(pos)]]
            
        def rightChildPos(self, pos):
            return 2*pos+2
            
        def rightChildVal(self, pos):
            return self.value[self.heap[self.rightChildPos(pos)]]
            
        def hasBiggerParent(self, pos):
            return self.hasParent(pos) and self.currentVal(pos) < self.parentVal(pos)
            
        def hasSmallerChild(self, pos):
            if self.hasTwoChilds(pos):
                return self.currentVal(pos) > self.leftChildVal(pos) or self.currentVal(pos) > self.rightChildVal(pos)
            if self.hasOneChild(pos):
                return self.currentVal(pos) > self.leftChildVal(pos)
            return False
            
        def isLeftChildSmaller(self, pos):
            if self.hasOneChild(pos):
                return True
            return self.leftChildVal(pos) < self.rightChildVal(pos)
            
        def switch(self, firstPos, secondPos):
            self.heap[firstPos], self.heap[secondPos] = self.heap[secondPos], self.heap[firstPos]
            self.index[self.heap[firstPos]] = firstPos
            self.index[self.heap[secondPos]] = secondPos
            
        def siftUp(self, pos):
            while self.hasBiggerParent(pos):
                self.switch(pos, self.parentPos(pos))
                pos = self.parentPos(pos)
            return pos
            
        def siftDown(self, pos):
            while self.hasSmallerChild(pos):
                if self.isLeftChildSmaller(pos):
                    self.switch(pos, self.leftChildPos(pos))
                    pos = self.leftChildPos(pos)
                else:
                    self.switch(pos, self.rightChildPos(pos))
                    pos = self.rightChildPos(pos)
            return pos
            
        def insert(self, key, value):
            self.heap.append(key)
            self.index[key] = len(self.heap)-1
            self.value[key] = value
            self.siftUp(len(self.heap)-1)
            
        def minimum(self):
            return self.heap[0]
            
        def delete(self, key):
            pos = self.index[key]
            self.switch(pos, len(self.heap)-1)
            self.heap.pop()
            self.index.pop(key)
            self.value.pop(key)
            self.siftDown(pos)
            
        def change(self, key, value):
            pos = self.index[key]
            self.value[key] = value
            self.siftUp(self.siftDown(pos))
            
H = Heap()
H.insert("Chemnitz", 4)
H.insert("Leipzig", 5)
H.insert("Dresden", 6)
H.insert("Freiberg", 2)
H.insert("Plauen", 8)
print(H)
H.delete(H.minimum())
print(H)
H.change("Chemnitz", 9)
print(H)
H.change("Chemnitz", 4)
print(H)