class HeapArray:
    
    def __init__(self):
        self._data = []
        self._size = 0
        
    def empty(self):
        return self._size == 0
    
    def __str__(self):
        return str(self._data)
    
    def insert(self,e):
        self._data.append(e)
        self._size = self._size + 1
        index = self._size - 1
        while index > 0 and self._data[index] <= self._data[(index-1)//2]:
            # swap
            temp = self._data[index]
            self._data[index] = self._data[(index-1)//2]
            self._data[(index-1)//2] = temp
            index = (index-1)//2
        return True  
        
    def delete_min(self):
        if self._size == 0:
            return None
        elif self._size == 1:
            m = self._data.pop(0)
            self._size = self._size - 1
            return m
        else: # we have 2 or more items in PQ
            m = self._data[0]
            self._data[0] = self._data.pop(self._size-1)
            self._size = self._size - 1
            index = 0
            while 2*index+1 <= self._size-1:   # not a leaf, i.e. there is at least one child 
                if 2*index+2 <= self._size-1: # has 2 children
                    if self._data[2*index+1] <= self._data[2*index+2]: #May have to swap with left child
                        if self._data[index] <= self._data[2*index+1]:
                            break
                        else: # swap with left child
                            temp = self._data[index]
                            self._data[index] = self._data[2*index+1]
                            self._data[2*index+1] = temp
                            index = 2*index+1
                    else: #may have to swap with right child
                        if self._data[index] <= self._data[2*index+2]:
                            break
                        else: # swap with right child
                            temp = self._data[index]
                            self._data[index] = self._data[2*index+2]
                            self._data[2*index+2] = temp
                            index = 2*index+2
                else: # 1 child
                    if self._data[index] > self._data[2*index+1]:
                        temp = self._data[index]
                        self._data[index] = self._data[2*index+1]
                        self._data[2*index+1] = temp
                        index = 2*index+1
                    else:
                        break  
            return m

p1 = HeapArray()
p1.insert(10)
p1.insert(17)
p1.insert(5)
p1.insert(3)
p1.insert(22)
p1.insert(19)
p1.insert(18)
p1.insert(1)
print(p1)
x = p1.delete_min()
print(x,p1)
x = p1.delete_min()
print(x,p1)
p2 = HeapArray()
x = p2.delete_min()
print(x,p2)

[1, 3, 10, 5, 22, 19, 18, 17]
1 [3, 5, 10, 17, 22, 19, 18]
3 [5, 17, 10, 18, 22, 19]
None []

x = 7
y = 9
temp = y
y = x
x = temp
print(x,y)

9 7

s = [10,20,30]
x = s.pop(2)
print(x,s)

30 [10, 20]

xs = [10,5,3,9,20,2,1]

ppp = HeapArray()
for x in xs:
    ppp.insert(x)
#print(p1)
ys = []
while not ppp.empty():
    ys.append(ppp.delete_min())
print(ys)

[1, 2, 3, 5, 9, 10, 20]

nlog(n)