Explain what the heap data structure is, state its defining properties and explain how to convert…

Explain what the heap data structure is, state its defining properties and explain how to convert between the tree and vector representations of a heap. [2 marks] (b) Describe an optimally efficient algorithm for transforming any random vector into a heap vector and explain why it works. [4 marks] (c) Using the tree instead of the vector representation for clarity, apply this algorithm to the binary tree isomorphic to the letter vector “P I S K T Z O P V N”, producing a frame-by-frame trace of the execution. For this answer, please use the sheet for part (c), supplied with the question paper, and use a new tree whenever any nodes change.