Part A: Heap Matrices $(30$ marks$)$

Background

The binary heap seen in class is implemented as linear array and can be used to represent an instance of the class Priority Queue. An alternate way to represent a Priority Queue is an $mn$ matrix where:

the items of each row are sorted in decreasing priority from left to right, and

the items of each column are sorted in decreasing priority from top to bottom.

The matrix therefore can hold at most $mn$ items. If there are fewer items, then the remaining locations are set to undefined $($e$.$g$.+$ or null$).$ We will call this special type of matrix a Heap matrix.

Example of a $45$ Heap matrix with $14$ integers:

$\backslash$table$[[17,33,67,87,99],[25,42,70,91,+$