import sys
import math

'''
I was unable to get this part of the project to work either. I followed the book for max-heapify but tried doing it for the min_heap.
I hope that even though I was unable to pass the test cases the grader will see that I was close and be generous. I understand
this is a lot to ask, but I put in many hours of work for the project. 


'''

class MinHeap:

	def __init__(self):
		self.s = 0
		self.hlist = [None]

	#look, to_String, size and is_empty are easy to implement
	def parent (self, i):
		return math.floor(i / 2)
	
	def insert(self, x):
		self.hlist.append(x)
		self.s += 1
		self.heapify(self.hlist[1]) #pass in the root to heapify

	def remove(self):
		if self.s == 1:
			return 
		else:
			x = self.hlist.pop(1)
			self.s -= 1
			self.build_min_heap()
			return x
		#I did not complete the 
	def look(self):
		if self.is_empty():
			return "HeapError"
		return self.hlist[1]

	def size(self):
		return self.s

	def is_empty(self):
		if self.s ==0:
			return True
		else: 
			return False

	def to_string(self):
		if self.is_empty():
			return "Empty"
		else:
			keys = ''
			for i in range(1, self.s):
				#print(str(hlist[i]))
				keys += str(self.hlist[i])
				keys += ' '
			keys += str(self.hlist[self.s])
			return keys

	def heapify(self, i): #taken from the book
		#print(i)
		if self.s < 3: #two elements in the heap, already sorted.
			return
		if self.s == 3:
			if self.hlist[1] > self.hlist[2]:
				temp = self.hlist[2]	#swap current with parent
				self.hlist[2] = self.hlist[1]
				self.hlist[1] = temp
				return
		l = 2 * i
		r = 2 * i + 1
		if l >= self.s and self.hlist[l] < self.hlist[r]:
			smallest = l
		else:
			smallest = i
		if r >= self.s and self.hlist[r] < self.hlist[smallest]:
			smallest = r
		if smallest != i:
			temp = self.hlist[i]	#swap current with parent
			self.hlist[smallest] = self.hlist[i]
			self.hlist[i] = temp

	def build_min_heap(self):
		h = math.floor(self.s / 2)
		for i in range(h,1,-1):
			print("print h", h)
			self.heapify(h)


def driver():
    m = MinHeap()
    with open(sys.argv[1]) as f:
        n = int(f.readline().strip())
        for _ in range(n):
            in_data = f.readline().strip().split()
            action, value_option = in_data[0], in_data[1:]

            if action == "print": 
            	print(m.to_string())
                
            elif action == "insert":
            	m.insert(value_option)

            elif action == "remove":
            	print(m.remove())

            elif action == "best":
            	print(m.look())

            elif action == "size":
            	print(m.size())

if __name__ == "__main__":
    driver()















2898b52fcbf01c12f17998c5f61a59aaa72af1a8
<mask token>


class MinHeap:

    def __init__(self):
        self.s = 0
        self.hlist = [None]

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

    def insert(self, x):
        self.hlist.append(x)
        self.s += 1
        self.heapify(self.hlist[1])

    def remove(self):
        if self.s == 1:
            return
        else:
            x = self.hlist.pop(1)
            self.s -= 1
            self.build_min_heap()
            return x
    <mask token>

    def size(self):
        return self.s
    <mask token>

    def to_string(self):
        if self.is_empty():
            return 'Empty'
        else:
            keys = ''
            for i in range(1, self.s):
                keys += str(self.hlist[i])
                keys += ' '
            keys += str(self.hlist[self.s])
            return keys

    def heapify(self, i):
        if self.s < 3:
            return
        if self.s == 3:
            if self.hlist[1] > self.hlist[2]:
                temp = self.hlist[2]
                self.hlist[2] = self.hlist[1]
                self.hlist[1] = temp
                return
        l = 2 * i
        r = 2 * i + 1
        if l >= self.s and self.hlist[l] < self.hlist[r]:
            smallest = l
        else:
            smallest = i
        if r >= self.s and self.hlist[r] < self.hlist[smallest]:
            smallest = r
        if smallest != i:
            temp = self.hlist[i]
            self.hlist[smallest] = self.hlist[i]
            self.hlist[i] = temp

    def build_min_heap(self):
        h = math.floor(self.s / 2)
        for i in range(h, 1, -1):
            print('print h', h)
            self.heapify(h)


<mask token>

<mask token>


class MinHeap:

    def __init__(self):
        self.s = 0
        self.hlist = [None]

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

    def insert(self, x):
        self.hlist.append(x)
        self.s += 1
        self.heapify(self.hlist[1])

    def remove(self):
        if self.s == 1:
            return
        else:
            x = self.hlist.pop(1)
            self.s -= 1
            self.build_min_heap()
            return x
    <mask token>

    def size(self):
        return self.s

    def is_empty(self):
        if self.s == 0:
            return True
        else:
            return False

    def to_string(self):
        if self.is_empty():
            return 'Empty'
        else:
            keys = ''
            for i in range(1, self.s):
                keys += str(self.hlist[i])
                keys += ' '
            keys += str(self.hlist[self.s])
            return keys

    def heapify(self, i):
        if self.s < 3:
            return
        if self.s == 3:
            if self.hlist[1] > self.hlist[2]:
                temp = self.hlist[2]
                self.hlist[2] = self.hlist[1]
                self.hlist[1] = temp
                return
        l = 2 * i
        r = 2 * i + 1
        if l >= self.s and self.hlist[l] < self.hlist[r]:
            smallest = l
        else:
            smallest = i
        if r >= self.s and self.hlist[r] < self.hlist[smallest]:
            smallest = r
        if smallest != i:
            temp = self.hlist[i]
            self.hlist[smallest] = self.hlist[i]
            self.hlist[i] = temp

    def build_min_heap(self):
        h = math.floor(self.s / 2)
        for i in range(h, 1, -1):
            print('print h', h)
            self.heapify(h)


<mask token>

<mask token>


class MinHeap:

    def __init__(self):
        self.s = 0
        self.hlist = [None]

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

    def insert(self, x):
        self.hlist.append(x)
        self.s += 1
        self.heapify(self.hlist[1])

    def remove(self):
        if self.s == 1:
            return
        else:
            x = self.hlist.pop(1)
            self.s -= 1
            self.build_min_heap()
            return x

    def look(self):
        if self.is_empty():
            return 'HeapError'
        return self.hlist[1]

    def size(self):
        return self.s

    def is_empty(self):
        if self.s == 0:
            return True
        else:
            return False

    def to_string(self):
        if self.is_empty():
            return 'Empty'
        else:
            keys = ''
            for i in range(1, self.s):
                keys += str(self.hlist[i])
                keys += ' '
            keys += str(self.hlist[self.s])
            return keys

    def heapify(self, i):
        if self.s < 3:
            return
        if self.s == 3:
            if self.hlist[1] > self.hlist[2]:
                temp = self.hlist[2]
                self.hlist[2] = self.hlist[1]
                self.hlist[1] = temp
                return
        l = 2 * i
        r = 2 * i + 1
        if l >= self.s and self.hlist[l] < self.hlist[r]:
            smallest = l
        else:
            smallest = i
        if r >= self.s and self.hlist[r] < self.hlist[smallest]:
            smallest = r
        if smallest != i:
            temp = self.hlist[i]
            self.hlist[smallest] = self.hlist[i]
            self.hlist[i] = temp

    def build_min_heap(self):
        h = math.floor(self.s / 2)
        for i in range(h, 1, -1):
            print('print h', h)
            self.heapify(h)


def driver():
    m = MinHeap()
    with open(sys.argv[1]) as f:
        n = int(f.readline().strip())
        for _ in range(n):
            in_data = f.readline().strip().split()
            action, value_option = in_data[0], in_data[1:]
            if action == 'print':
                print(m.to_string())
            elif action == 'insert':
                m.insert(value_option)
            elif action == 'remove':
                print(m.remove())
            elif action == 'best':
                print(m.look())
            elif action == 'size':
                print(m.size())


if __name__ == '__main__':
    driver()

import sys
import math
<mask token>


class MinHeap:

    def __init__(self):
        self.s = 0
        self.hlist = [None]

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

    def insert(self, x):
        self.hlist.append(x)
        self.s += 1
        self.heapify(self.hlist[1])

    def remove(self):
        if self.s == 1:
            return
        else:
            x = self.hlist.pop(1)
            self.s -= 1
            self.build_min_heap()
            return x

    def look(self):
        if self.is_empty():
            return 'HeapError'
        return self.hlist[1]

    def size(self):
        return self.s

    def is_empty(self):
        if self.s == 0:
            return True
        else:
            return False

    def to_string(self):
        if self.is_empty():
            return 'Empty'
        else:
            keys = ''
            for i in range(1, self.s):
                keys += str(self.hlist[i])
                keys += ' '
            keys += str(self.hlist[self.s])
            return keys

    def heapify(self, i):
        if self.s < 3:
            return
        if self.s == 3:
            if self.hlist[1] > self.hlist[2]:
                temp = self.hlist[2]
                self.hlist[2] = self.hlist[1]
                self.hlist[1] = temp
                return
        l = 2 * i
        r = 2 * i + 1
        if l >= self.s and self.hlist[l] < self.hlist[r]:
            smallest = l
        else:
            smallest = i
        if r >= self.s and self.hlist[r] < self.hlist[smallest]:
            smallest = r
        if smallest != i:
            temp = self.hlist[i]
            self.hlist[smallest] = self.hlist[i]
            self.hlist[i] = temp

    def build_min_heap(self):
        h = math.floor(self.s / 2)
        for i in range(h, 1, -1):
            print('print h', h)
            self.heapify(h)


def driver():
    m = MinHeap()
    with open(sys.argv[1]) as f:
        n = int(f.readline().strip())
        for _ in range(n):
            in_data = f.readline().strip().split()
            action, value_option = in_data[0], in_data[1:]
            if action == 'print':
                print(m.to_string())
            elif action == 'insert':
                m.insert(value_option)
            elif action == 'remove':
                print(m.remove())
            elif action == 'best':
                print(m.look())
            elif action == 'size':
                print(m.size())


if __name__ == '__main__':
    driver()

import sys
import math

'''
I was unable to get this part of the project to work either. I followed the book for max-heapify but tried doing it for the min_heap.
I hope that even though I was unable to pass the test cases the grader will see that I was close and be generous. I understand
this is a lot to ask, but I put in many hours of work for the project. 


'''

class MinHeap:

	def __init__(self):
		self.s = 0
		self.hlist = [None]

	#look, to_String, size and is_empty are easy to implement
	def parent (self, i):
		return math.floor(i / 2)
	
	def insert(self, x):
		self.hlist.append(x)
		self.s += 1
		self.heapify(self.hlist[1]) #pass in the root to heapify

	def remove(self):
		if self.s == 1:
			return 
		else:
			x = self.hlist.pop(1)
			self.s -= 1
			self.build_min_heap()
			return x
		#I did not complete the 
	def look(self):
		if self.is_empty():
			return "HeapError"
		return self.hlist[1]

	def size(self):
		return self.s

	def is_empty(self):
		if self.s ==0:
			return True
		else: 
			return False

	def to_string(self):
		if self.is_empty():
			return "Empty"
		else:
			keys = ''
			for i in range(1, self.s):
				#print(str(hlist[i]))
				keys += str(self.hlist[i])
				keys += ' '
			keys += str(self.hlist[self.s])
			return keys

	def heapify(self, i): #taken from the book
		#print(i)
		if self.s < 3: #two elements in the heap, already sorted.
			return
		if self.s == 3:
			if self.hlist[1] > self.hlist[2]:
				temp = self.hlist[2]	#swap current with parent
				self.hlist[2] = self.hlist[1]
				self.hlist[1] = temp
				return
		l = 2 * i
		r = 2 * i + 1
		if l >= self.s and self.hlist[l] < self.hlist[r]:
			smallest = l
		else:
			smallest = i
		if r >= self.s and self.hlist[r] < self.hlist[smallest]:
			smallest = r
		if smallest != i:
			temp = self.hlist[i]	#swap current with parent
			self.hlist[smallest] = self.hlist[i]
			self.hlist[i] = temp

	def build_min_heap(self):
		h = math.floor(self.s / 2)
		for i in range(h,1,-1):
			print("print h", h)
			self.heapify(h)


def driver():
    m = MinHeap()
    with open(sys.argv[1]) as f:
        n = int(f.readline().strip())
        for _ in range(n):
            in_data = f.readline().strip().split()
            action, value_option = in_data[0], in_data[1:]

            if action == "print": 
            	print(m.to_string())
                
            elif action == "insert":
            	m.insert(value_option)

            elif action == "remove":
            	print(m.remove())

            elif action == "best":
            	print(m.look())

            elif action == "size":
            	print(m.size())

if __name__ == "__main__":
    driver()














