Heaps

Question 1

Heap definition

Answer 1

A specialized tree with two properties:
Structure property: Is a complete binary tree. No empty nodes except the right side of the last row.
Order property: The entire subtree under a node is all less/more than the node.

Question 2

Time complexity
Create?
Push?
Pop?

Answer 2

O(n) to heapify
O(logn) to push/pop

Question 3

Algorithm to push

Answer 3

Insert at the end of the array, then percolate up/down by comparing element to its parent and swapping if necessary, recursively.

Question 4

Algorithm to pop

Answer 4

Copy the last element in the array to the root, then percolate it down to its proper place.