Heap

Question 1

What is a Heap

Answer 1

A complete tree with the heap order property

Question 2

what is the heap order property

Answer 2

the key stored at v is >= the key stored at vs parent

Question 3

which node is the last node

Answer 3

the rightmost deepest node

Question 4

what is the height of a heap

Answer 4

log(n+1)

Question 5

why is vector representation a good way to store a heap

Answer 5

because it is complete

Question 6

describe min heap

Answer 6

smallest item is at the top and increase going down

Question 7

what does it mean to bubble up

Answer 7

when we insert, we then have to bubble up. this is done by swapping parent and child to preserve heap order

Question 8

how do we remove min

Answer 8

the min is always the root.

replace the root with the last element to preserve completeness and bubble down to preserve heap order

Question 9

can we store a heap using a linked structure? why?

Answer 9

no because we want to know where the last element is