Priority Queues and Heapsort

Which of the following are min heaps?

• A

• B

• C

• D

The 2 properties of a min heap are _____.

• Tree must be full.

• Tree must be complete.

• Node values are always smaller than their children's values.

• Node values are always greater than their children's values.

How many swaps are made in the min heap when inserting the value 18?

• 0

• 1

• 2

• 3

What is the efficiency of adding to a priority queue using the java.util.PriorityQueue class?

• O(n)

• O(n log n)

• O(1)

• O(log n)

What operation has efficiency O(1) using the java.util.PriorityQueue class?

• Add

• Remove

• Peek

Which of the following PriorityQueue<E> methods will throw an exception when used on an empty queue?

• E remove()

• E peek()

• E element()

• E poll()

When removing the root from a min heap, what is the first step?

• Replace the root with the next smallest value from the tree

• Replace the root with the leaf furthest to the left on the bottom level of the tree

• Replace the root with the leaf furthest to the right on the bottom level of the tree

• Replace the root with the smallest of its children

The formula for finding the right child of a node in a heap stored in an array is ________ . (The root is at index 0)

• ( 2 * Parent ) + 2

• ( Parent / 2 ) + 2

• ( 2 * Parent ) + 1

• ( Parent - 2 ) / 2

The formula for finding the parent of a node in a heap stored in an array is ________ . (The root is at index 0)

• ( 2 * Child ) / 2

• ( 2 * Child ) - 1

• ( Child – 1 ) / 2

• ( Child + 1 ) / 2

When adding a value to a min heap, the first step is to ______.

• Add the new node at the next open leaf position.

• Replace the root's value with the new value.

• Replace the roots smallest child with the new value.