Now that we have learnt about heap and heap-sort, it's time to implement them. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let's get started!

# Implementing Heap and Heap-sort

## Python

Below, we provide a short Python code template for you to implement heap and heap-sort.

# heap_sort.py# calculate index of parent, left child, right childROOT = 1def parent(index):return # TODOdef left_child(index):return # TODOdef right_child(index):return # TODO# Heap() classclass Heap():# heap data is stored in self.data# first item of self.data is None so that the actual first item is at position 1def __init__(self):self.data = [None]def insert(self, element):# TODO: add element to end of heap# TODO: upward-swapsreturn Truedef pop(self):assert len(self.data) > 1# store original rootresult = self.data[ROOT]# TODO: move last element to root# TODO: downward-swaps# return original rootreturn resultdef heap_sort(array):heap = Heap()# insert everything into heapfor element in array:heap.insert(element)# pop everything from heapresult = list()for ii in range(len(array)):element = heap.pop()result.append(element)return result# testarray = [5, 10, 8, 7, 3, 7, 6, 12, 2, 7]result = heap_sort(array)assert result == [2, 3, 5, 6, 7, 7, 7, 8, 10, 12], result

## C++, Java, etc

If you're not using Python, have your implementation accept test cases from standard input, and print results to standard output.

**Input description:** The first line contains the number of test cases T. This is followed by T lines. Each line starts with a number N, the size of the array. On the same line, the N numbers of the array are listed one after the other.

**Sample input:**

23 227 198 1910 458 687 945 378 479 421 33 295 922 840

**Output description: **Output should contain T lines. Each line should just contain the numbers in sorted order, separated by spaces.

**Sample output:**

19 198 22733 295 378 421 458 479 687 840 922 945

## Notes

The trickiest part about implementing heaps is the upward and downward swaps. Specifically, be careful about when to stop swapping, and which child to swap with (when swapping downwards). Also, debugging these things needs patience.