# 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
• order by priority (highest priority item first)
• DeleteMax is a remove-from-front(cost O(1))
• Insert is an ordered insert(cost O(n)
• 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:

1. What is the index of the left child?
2. right child?
3. 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
15
Q
A
16
Q
A
17
Q

What is the code for insert (including the priority queue class)?

A
18
Q

What is the code for siftUp?

A
19
Q

What is the code for swap?

A
20
Q

In general how doe DeleteMax work?

A
• Save the item in the roon (heap[0]), because it has the highest priority, so we will want to return it.
• Take the item I in heap[heapSize-1] (bottom of the heap) and place it in the root, and decrement heapSize.
• We must restore heap order in the heap: item I (which we just placed in the root) may be less than one or both of its children since an item fomr the bottom of the heap will have a low priority.
• To restore heap order: sift down the root (repeatedly swap I with the larger of it’s two children (if it has two) or it’s sole child (if only one) until either:
• I is larger than it’s two children(or than it’s sole and only child) or
• I has no children
21
Q

DeleteMax the following heap

A
22
Q
A
23
Q
A
24
Q
A
25
Q

What is the code for deleteMax?

A
26
Q

What is the code for siftDown?

A
27
Q

What is the run time of insert and deleteMax?

A