Chapter 6 (Priority Queues (Heaps))

Question 1

What is the big-O time to search for a min in a linked list?

Answer 1

O(n) since you might have to search the whole list

Question 2

What is the insert and remove min for a binary heap?

Answer 2

O(log n)

Question 3

When is a binary tree complete?

Answer 3

Every node has two children except the last level which is filled from left to right

Question 4

How does a sorted linked list affect the search for a min and inserting?

Answer 4

Search for a min becomes O(1) since it’s sorted, but insert becomes O(n) because it may have to traverse to the end of the list for the insert.

Question 5

T/F The npl of any node is two more than the minimum npl’s of its children

Answer 5

F, one more

Question 6

What is the NPL of a null?

Answer 6

-1

Question 7

Where is the maximum value in the heap-order property?

Answer 7

In a leaf node

Question 8

What’s the difference between a leftist heap and skew heap?

Answer 8

The skew heap does not compare left and right subtree’s, it always swaps after a merge no matter what.

Question 9

T/F The structure of a heap is a binary tree that is completely filled except possibly the bottom level, which is filled left to right

Answer 9

T

Question 10

What are two operations that a priority queue, at the minimum, supports?

Answer 10

Insert (enqueue) and deleteMin (similar to dequeue)

Question 11

When is a binary tree perfect?

Answer 11

Has exactly 2^(h+1)-1 nodes where h is the height

Question 12

What does a delete need?

Answer 12

decreaseKey to minimum then deleteMin

Question 13

Since there are at most log N different trees, each with its minimum at its root, the heap’s minimum can be found in ____ time

Answer 13

O(log N)

Question 14

Leftist heaps use a ____ of a node, which is the length of the shortest path from the node to a node without two children

Answer 14

“null path length”

Question 15

What is the NPL of a node with 0 or 1 child?

Answer 15

0

Question 16

What does decreaseKey require?

Answer 16

Percolate up

Question 17

With the heap-order property, what is the running time for the findMin operation?

Answer 17

O(1)

Question 18

What does increasKey require?

Answer 18

Percolate down

Question 19

What two things have to be done for deleteMin?

Answer 19

Remove the root value Re-arrange the heap to preserve the heap-order property

Question 20

What is a d-heap?

Answer 20

Has d children per parent

Question 21

What is the running time of buildHeap?

Answer 21

O(N)

Question 22

T/F Each item in a queue is treated equally

Answer 22

T

Question 23

What is the advantage of a d-heap having d children?

Answer 23

Results in a shallower tree, which improves performance of inserts

Question 24

What two things must be done for an insert with a binary heap?

Answer 24

Insert into the next available node Re-arrange the heap to preserve the heap-order property

Question 25

What is the leftist heap property?

Answer 25

For every node, the npl of its left child is at least as large as the npl of its right child

Question 26

A right child’s number is ____ its parent’s number

Answer 26

2X+1

Question 27

When is a binary tree full?

Answer 27

Every node is either a leaf or has two children

Question 28

What are leftist heaps designed to support?

Answer 28

Efficient merging of two heaps

Question 29

What does buildHeap do?

Answer 29

Takes N items and builds a heap

Question 30

What type of data structure is a queue?

Answer 30

FIFO

Question 31

What is the heap-order property?

Answer 31

Any node should be smaller than all of its descendants

Question 32

What is the running time of insert and remove min for a balanced search tree?

Answer 32

O(log n)

Question 33

What is “percolate up”?

Answer 33

Create a node, check ordering, if not OK then swap with parent, repeat until the node is in its proper position

Question 34

A complete binary tree of height h always has between ____ and ____ nodes, which leads to performance of ____

Answer 34

2^h, 2^(h+1)-1, O(log N)

Question 35

T/F A priority queue is a data structure that orders its items by priority

Answer 35

T

Question 36

What other heap operations might we have?

Answer 36

decreaseKey increaseKey delete buildHeap

Question 37

Binomial queues are essentially a forest of heap-ordered trees where each tree of height k has exactly ____ nodes, and there can be at most one tree of each height

Answer 37

2^k

Question 38

What is “percolate down”?

Answer 38

Repeat sliding the hole node down until the last node value can occupy this node while preserving the heap-order property

Question 39

Binomial queues have ____ time on insert, deleteMin, and merge, but have ____ average time on an insert

Answer 39

O(log N), O(1)

Question 40

What is the disadvantage of a d-heap having d children?

Answer 40

deleteMin may suffer because finding minimum child of a node is now harder

Question 41

What are the advantages of storing a heap in an array?

Answer 41

No links (pointers), operations to traverse are fast

Question 42

A left child’s number is ____ its parent’s number

Answer 42

2X

Question 43

Any parent number is ____

Answer 43

X/2