Heaps

Question 1

True or false, when we remove the min/max of a tree, we don’t need to maintain the completeness of the tree.

Answer 1

False. We need to find the new min and set that as the new root

Question 2

The parent of a node at index i is at index ________ (using the floor that results from integer division).

Answer 2

(i - 1) // 2 (i.e. floor)

Question 3

What is the five step process for removing a node

Answer 3

1. Remember the value of the first element in the array (to be returned later). 2. Replace the value of the first element in the array with the value of the last element and remove the last element. 3. If the array is not empty (i.e., it started with more than one element), compute the indices of the children of the replacement element (2 * i + 1 and 2 * i + 2). ( If both of these elements fall beyond the bounds of the array, we can stop here.) 4. Compare the value of the replacement element with the minimum value of its two children (or possibly one child). 5. If the replacement element’s value is greater than its minimum child’s value, swap those two elements in the array, and repeat from step 3.

Question 4

After we remove the min/max node from a heap, the we first replace that the root with _____

Answer 4

the last node. In an array, this is the last element.

Question 5

We can efficiently IMPLEMENT the complete binary tree representation of a heap using a/an _______. Can any binary tree be represented using this?

Answer 5

array or dynamic array. Yes.

Question 6

Whats the pseudocode while loop for percolating a node down for when you remove a node from the heap?

Answer 6

while priority > smallest child priority: swap with smallest child where priority is the new root node, and smallest child priority is the smallest child of that node

Question 7

In a priority queue, whats the first element that gets dequeued?

Answer 7

The element with the highest priority

Question 8

Whats the fundamental idea of the priority queue ADT

Answer 8

The priority queue is an ADT that associates a priority value with each element.

Question 9

What happens if we use an array to implement a binary tree but the tree isn’t complete

Answer 9

If the binary tree isn’t complete, then the array will be less space efficient because there will be gaps in the array

Question 10

What data structure is typically used to implement a priority queue?

Answer 10

A heap

Question 11

Pseudocode for removing minimum value from an array based heap

Answer 11

1. Remember the value of the first element in the array (to be returned later).
2. Replace the value of the first element in the array with the value of the last element and remove the last element.
3. If the array is not empty (i.e., it started with more than one element), compute the indices of the children of the replacement element (2 * i + 1 and 2 * i + 2).
   
   • If both of these elements fall beyond the bounds of the array, we can stop here.
4. Compare the value of the replacement element with the minimum value of its two children (or possibly one child).
5. If the replacement element’s value is greater than its minimum child’s value, swap those two elements in the array, and repeat from step 3.

Question 12

Does a heap maintain BST property where the left child is smaller and right child is bigger?

Answer 12

No. It just has to be a complete tree.

Question 13

What are the two requirements for a minimizing heap data structure (or min heap)

Answer 13

Must be a COMPLETE binary tree EVERY NODE’S value must be less than or equal to the values of its children

Question 14

In a min or max heap, which node is always the lowest or max value?

Answer 14

The root of the tree

Question 15

Where is the lowest priority value located in a min heap?

Answer 15

The root node

Question 16

What operation do you use for adding a node? Percolate down or up the tree?

Answer 16

Up

Question 17

The _______ is an ADT that associates a priority value with each element. A ________ data structure is a complete binary tree in which every node’s value is less than or equal to the values of its children. A ___________ is typically implemented using a data structure called a ________.

Answer 17

priority queue min heap priority queue heap

Question 18

Whats the n-step process for removing the root node from a heap?

Answer 18

1. Remove the root node 2. Replace the root node with with whatever the last element in the heap 3. Fix the heap by percolating that node down

Question 19

In an array-implemented heap, where is the last element and the “next open spot” in the heap

Answer 19

Last element is literally last element in the array, and next open spot is the index that follows after the last element in the array

Question 20

Using an array to implement a binary tree that is not complete is bad because

Answer 20

It can leave big gaps in the array, wasting space.

Question 21

When we add a new value to a min heap, we place it into the ________ and then percolate it ____ until its priority value is _____ than both of its children.

Answer 21

“next open spot”, up, less

Question 22

True or false, in an array representation of a heap, the order of the nodes in the array follows the breadth first search results

Answer 22

True.

Question 23

Pseudocode for inserting into an array based heap

Answer 23

• Put new element at the end of the array.
• Compute the inserted element’s parent index ((i - 1) / 2).
• Compare the value of the inserted element with the value of its parent.
• If the value of the parent is greater than the value of the inserted element, swap the elements in the array and repeat from step 2 else stop.
  
  • Do not repeat if the element has reached the beginning of the array.

Question 24

Whats the pseducode for percolating down the replacement node after removing the root node from a heap?

Answer 24

while priority > smallest child:

swap with smallest child

Question 25

Which operation do you use for removing a node? Percolate down or up the tree?

Answer 25

Down

Question 26

Whats the four step pseudocode process for inserting an element into the heap

Answer 26

1. Put new element at the end of the array. 2. Find the index of the parent of the inserted element ((i - 1) / 2) 3. Compare the value of the inserted element with the value of its parent. 4. If the value of the parent is greater than the value of the inserted element, swap the elements in the array and repeat from step 2. Loop stops when #4 is false or the inserted element ends up at the beginning of the array

Question 27

The last node at the deepest level in the heap is located where in the array?

Answer 27

The very last element of the array.

Question 28

When removing a node from a MIN heap, what’s the node that gets removed?

Answer 28

Since the min heap is a tree, the root node is the lowest value in a min heap. The root node is the only node that ever gets removed in a min heap (and max heap)

Question 29

A min (or max) heap is maintained through the addition and removal of nodes via ________, which move nodes up and down the tree according to their priority values.

Answer 29

percolations

Question 30

In an array representation of a heap, the left and right children of a node at index i are stored at indices _________ and , respectively.

Answer 30

left: 2 * (i + 1), right: 2 * (i + 2)

Question 31

Whats the pseudocode while loop for percolating a node up when you ADD a node to the heap

Answer 31

while new priority value < parent’s priority value: swap new node with parent

Question 32

In an array representation of a heap, where is the root node stored?

Answer 32

Index 0

Question 33

When we add a new value to a heap, we always first add it at the ____ which is located ______

Answer 33

“next open spot”, which is in the last level to the right of the furthest left node