# Priority Queues and Heaps Flashcards

1

Q

What is a priority queue and what are it’s operations?

A

2

Q

What are the applications of a priority Queue?

A

Hospital emergency room

Event-Driven simulations

3

Q

How does a priority queue compare to a queue?

A

4

Q

What are the implementations of a priority queue, what are their speeds of operations and which is the best?

A

- Array or LinkedList
- order by priority (highest priority item first)
- DeleteMax is a remove-from-front(cost O(1))
- Insert is an ordered insert(cost O(n)

- order by priority (highest priority item first)
- Binary search tree (BST) The highest priority item is in the rightmost descendant of the root
- DeleteMax and Insert are O(n) (unless you use some sort of balanced tree (O(n)).

- Best-> a Heap: A binary tree - but not a BST - stored in an array
- DeleteMax and Insert are O(log n)

5

Q

What is the definition of a full tree?

A

6

Q

Define a complete tree

A

7

Q

What is the definition of heap ordered?

A

8

Q

A

9

Q

What is the definition of a heap

A

10

Q

In general how is an array used to implement a heap?

A

11

Q

With no pointers, how do we find a node’s children?

A

12

Q

If 35 is stored in array index 5:

- What is the index of the left child?
- right child?
- What is the index of it’s parent?

A

13

Q

A

14

Q

In general how do heap insertions work?

A

- First, place the new item in heap[heapSize] and increment heap size.
- The heap may not be heap ordered now (new item might be larger than parent)

- We need to sift up the new item towards the root
- repeatedly exchange the new item with it’s parent until either:
- It’s parent is larger than the new item, or
- The new item is the root

- repeatedly exchange the new item with it’s parent until either:

15

Q

A