Binary Heaps & Priority Queues

Question 1

What are the API methods for a binary heap

Answer 1

Push(v)
Min()
Pop()
Size()
Empty()
Clear()

Question 2

Define what a heap is

Answer 2

A complete binary tree, where every level will be full, except for the last, irrelevant of values of the elements. The last level must also be filled left to right first

Question 3

What is the main property of a heap’s organization

Answer 3

The value of each node must be less than or equal to all of the values in its sub trees.

Question 4

Are duplicate values allowed in heaps

Answer 4

yes

Question 5

What must be done when inserting a new value into a heap

Answer 5

You must percolate up and make sure that the newly inserted value is less than or equal to each value below it. The new node will start at the right most open spot on the last level

Question 6

What is one reason one would chose a heap over a multiset

Answer 6

The heap is more memory efficient and equally as time efficient

Question 7

What is the run time complexity of making a heap from a vector

Answer 7

O(n)