Priority Queue and Heap

Question 1

What is the runtime of insert?

Answer 1

log(n)

Question 2

What is the runtime of deleteMin (or deleteMax depending on priority)?

Answer 2

log(n)

Question 3

What can priority queue not do?

Answer 3

No searching, no sorting.

Question 4

Why do the operations get log time?

Answer 4

Because we use a heap and because of the following setup of the array:
left child: 2i (i being the element we’re currently at)
right child: 2i+1
your parent: i/2 (integer math so chops off the decimal)

Question 5

What does heap look like?

Answer 5

It looks like a binary tree, but it is an array.

Question 6

What is the heap implemented by?

Answer 6

Heap is implemented by using an array, NOT A LINKED LIST.

Question 7

What is the priority queue implemented by?

Answer 7

Implemented by using heap (the structure).

Question 8

What is min heap?

Answer 8

Everything under is bigger

Question 9

What is max heap?

Answer 9

Everything under is smaller

Question 10

Where do we start when inserting?

Answer 10

We start at the bottom when inserting. A hole is added to the end and moved up.

Question 11

Where do we start when deleting?

Answer 11

We start at the top when deleting. A hole is added to the top and moved down. We always take off the top.