class PriorityQueue():
    def __init__(self, initial_elements):
        self.pq = []
        self.size = 0
        for element in initial_elements:
            self.insert(element)

    def swapPositions(self, pos1, pos2):
        temp=self.pq[pos1]
        self.pq[pos1]=self.pq[pos2]
        self.pq[pos2]=temp

    def heapify_bottom_up(self, idx):
        while idx > 0:
            parent = (idx-1)//2
            if self.pq[idx][0] > self.pq[parent][0]:
                self.swapPositions(idx, parent)
            else:
                break


    def heapify_top_down(self):
        idx = 0
        while idx<self.size:
            l = idx*2+1
            r = idx*2+2

            if l >=self.size:
                return
            if r >=self.size:
                if self.pq[l][0] > self.pq[idx][0]:
                    swapPositions(idx, l)
                    idx = l
                else:
                    return

            left_priority = self.pq[l][0]
            right_priority = self.pq[r][0]

            left_value = self.pq[l][1]
            right_value = self.pq[r][1]

            if self.pq[idx][0] > left_priority and self.pq[idx][0] > right_priority:
                return
            if right_priority > left_priority and right_priority > self.pq[idx][0]:
                self.swapPositions(idx, r)
                idx = r
            if left_priority > right_priority and left_priority > self.pq[idx][0]:
                self.swapPositions(idx, l)
                idx = l



    def insert(self, element):
        self.pq.append(element)
        self.size += 1
        self.heapify_bottom_up(self.size-1)

    def delete_root(self):
        self.pq[0] = self.pq[-1]
        self.size -= 1
        self.pq.pop()
        self.heapify_top_down()

    def get_max(self):
        top = self.pq[0]
        self.delete_root()
        return top
    def print(self):
        for i in self.pq:
            print(i)


q = PriorityQueue([(4, "Applied Algorithms")])
q.insert((1, "Database Design"))
q.insert((2, "Data Science"))


q.print()
k, v = q.get_max()
print(v)
k, v = q.get_max()
print(v)
k, v = q.get_max()
print(v)


print()
print()