"""
Part 1: Python Max-Priority Queue

This module implements a Max-Priority Queue in Python.

A priority queue is a data structure that allows elements to be inserted with an associated priority,
and supports efficient retrieval and removal of the element with the highest priority. In a max-priority queue,
the element with the largest priority value is always served before others.

Typical operations include:
- Insertion of elements with a priority
- Retrieval of the maximum-priority element
- Removal of the maximum-priority element

Priority queues are commonly used in scheduling, graph algorithms (like Dijkstra's and Prim's), and other applications
where ordering by priority is required.

You will now implement a simple priority that stores only the integer keys. 
The priority queue will be implemented using a max-heap, which is a binary tree 
where each parent node is greater than or equal to its children.

You are not allowed to use the built-in heapq.
"""

class MaxHeap:
    def __init__(self):
        self.heap = []

    def insert(self, key):
        """
        Insert a new integer key into the max-heap. 
        After inserting the new key, 
        you should sift it up to maintain the max-heap property.
        You can add any helper methods you need to implement the sift-up operation.
        """
        pass

    def pop(self):
        """
        Remove and return the maximum key from the max-heap.
        If there are no keys in the heap, return None.
        After removing the maximum key, you should replace it with the last key in the heap 
        and then sift it down to maintain the max heap property.
        You can add any helper methods you need to implement the sift-down operation.
        """
        pass
        

if __name__ == "__main__":
    # You can change the code below to test your implementation of the MaxHeap class.
    # Example usage:
    max_heap = MaxHeap()
    
    max_heap.insert(27)
    max_heap.insert(89)
    max_heap.insert(-29)
    max_heap.insert(13)
    max_heap.insert(83)
    max_heap.insert(-48)
    max_heap.insert(-9)
    max_heap.insert(-50)
    max_heap.insert(2)
    max_heap.insert(26)

    for _ in range(11):
        print(max_heap.pop())