Priority Queues and Heaps

Question 1

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

Answer 1

Question 2

What are the applications of a priority Queue?

Answer 2

Hospital emergency room

Event-Driven simulations

Question 3

How does a priority queue compare to a queue?

Answer 3

Question 4

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

Answer 4

• 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)
• 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)

Question 5

What is the definition of a full tree?

Answer 5

Question 6

Define a complete tree

Answer 6

Question 7

What is the definition of heap ordered?

Answer 7

Question 8

Answer 8

Question 9

What is the definition of a heap

Answer 9

Question 10

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

Answer 10

Question 11

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

Answer 11

Question 12

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?

Answer 12

Question 13

Answer 13

Question 14

In general how do heap insertions work?

Answer 14

• 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

Question 15

Answer 15

Question 16

Answer 16

Question 17

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

Answer 17

Question 18

What is the code for siftUp?

Answer 18

Question 19

What is the code for swap?

Answer 19

Question 20

In general how doe DeleteMax work?

Answer 20

• 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

Question 21

DeleteMax the following heap

Answer 21

Question 22

Answer 22

Question 23

Answer 23

Question 24

Answer 24

Question 25

What is the code for deleteMax?

Answer 25

Question 26

What is the code for siftDown?

Answer 26

Question 27

What is the run time of insert and deleteMax?

Answer 27