Mod 7

Question 1

Describe a priority queue.

Answer 1

The** priority queue **is an ADT that associates a priority value with each element. The element with the highest priority is the first one dequeued.
- insert() – insert an element with a specified priority value
- first() – return the element with the lowest priority value (the “first” element in the priority queue)
- remove_first() – remove (and return) the element with the lowest priority value

Question 2

What is the pseudocode for bubbling up or down a heap?

Answer 2

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

while priority > smallest child priority:
swap with smallest child

Question 3

What are the formula for right child, left child, and parent in a heap?

Answer 3

• right child = 2i+2
• left child = 2i + 1
  -parent = (i-1)//2

Question 4

Why do we use an array for a heap but not other binary trees?

Answer 4

By bubbling up and down, a heap is always complete. A complete tree does not have any gaps when represented as an array. Thus, an array can efficiently represent a heap but is inefficient for other trees.

Question 5

What are the steps for inserting into a heap?

Answer 5

1. Put the new element at the end of the array.
2. Compute the inserted element’s parent index, (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.

Question 6

What are the steps for removing from a heap?

Answer 6

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 6

How would you efficiently build a heap out of an array?

Answer 6

We percolate down the first non-leaf element (n//2)-1. Then the subtree rooted at that element’s original position will be a proper heap.

e can repeat this, moving backwards one element at a time from the first non-leaf element, and each time we percolate an element down, the subtree rooted at that element’s original position will be a proper heap.

Once we percolate down the root element, the entire array will represent a proper heap.

Question 7

How is heapsort implemented?

Answer 7

1. The first thing heapsort does is build a heap out of the array.
2. Then, to complete the sort, we use a procedure similar to our heap removal operation above, with a few small tweaks:
   - Keep a running counter k that is initialized to one less than the size of the array (i.e., the last element).
   - Instead of replacing the first element in the array (the min) with the last element (the kth element), we swap those two elements in the array.
   - The array itself remains the same size, and we decrement k.
   When percolating the replacement value down to its correct place in the array, we do not go beyond k-1.
   Thus, the heap portion is effectively shrinking by 1 with each iteration.