$($a$)$ Explain the terms:

i$)$ priority queue

ii$)$ complete binary tree

iii$)$ heap

iv$)$ heap condition

$($b$)$ Draw the following heap array as a two$-$dimensional binary tree data structure:

Also, assuming another array hPos$[]$ is used to store the position of each key in the

heap, show the contents of hPos$[]$ for this heap.

$(6$ marks$)$

$($c$)$ Write in pseudocode the algorithms for the siftUp$()$ and insert$()$ operations on a heap

and show how hPos$[]$ would be updated in the siftUp$()$ method if it was to be included

in the heap code. Also write down the complexity of siftUp$().$

$(9$ marks$)$

$($d$)$ By using tree and array diagrams, illustrate the effect of inserting a node whose key is

$12$ into the heap in the array of part $($b$).$ You can ignore effects on hPos$[].$

$(6$ marks$)$

$($e$)$ Given the following array, describe with the aid of text and tree diagrams how it might

be converted into a heap.