Week 8

Question 1

What is a heap?

Answer 1

A heap is a tree based data structure. Mainly used for priority queues and order statistics.

Question 2

What are the different types of heaps?

Answer 2

Binary heaps
Binomial heaps
Fibonnacci heaps

Question 3

What is a binary heap?

Answer 3

A complete binary tree, which is a binary tree in which all the levels are completely filled except possibly the lowest one which is filled from the left.

Question 4

How can a binary heap be implemented as a Max heap?

Answer 4

The largest element is always the root node.

The value of each nodeis greater than the value of its children.

The tree is complete.

The tree is perfectly balanced.

The leaf nodes in the last level are all pushed to the left.

Height is O(log n)

Question 5

How can we implement a heap as a min heap?

Answer 5

Similar to max except the value of each node is less than the value of its children.

The root contains the smallest element.

Question 6

Are heaps perfectly ordered?

Answer 6

No, heaps are not perfectly ordered.

Order is only maintained through linear lines of descent between parent and children only.

Question 7

How can heaps be implemented in arrays?

Answer 7

Elements are stored from top to bottom and from left to right at each level.

The root node is always at index = 0.

Question 8

In an array heap, at where is the position of the left child and the right child if the node index is i?

What is the position of a parent of a node at index = 1?

Answer 8

The position of the left child is 2i+1

The position of the right child is 2i+2

The position of the parent of the node is (i-1)/2

Question 9

How can a heap be implemented in a priority Queue?

Answer 9

Enqueue procedure:
add the new element to the end of the heap.

If necessary restore the heap property by swapping the element with its parent until the proper position is found or we are at the root.

Dequeue procedure
Remove the root element (highest priority)
Replace it with the last leaf node.

If necessary restore the heap property by swapping the rooy with its larger child, (reheaping downwards).

Question 10

What is the complexity of top up heap creation in the worst case?

Answer 10

O(nlogn)

Question 11

What is the worst case complexity for bottom up heap creation.

Answer 11

O(n) is the worst case.

Question 12

What are the steps for top down heap creation.

Answer 12

Start with empty heap
Sequentially enqueue new elements

Question 13

What are the steps for bottom up heap creation.

Answer 13

1. Start with the last non-leaf node (n/2)-1
2. Set index to this position
3. If necessary restore the heap property by swapping with the largest child.
4. Repeat until proper place found or becomes a leaf node.
5. Repeat step 2 after decrementing index. Stop once the root has been processed.

Question 14

What is heapsort? What is the procedure?

Answer 14

Is an inplace sort of an array.

Procedure:
Reorganize the array into a Max heap
Bottom up method is quickest
for (i = n-1; i>0; i–)
Swap root with element i
Restore heap property for elements 0 to i-1

Question 15

In heapsort, what is the worst case, average case and best case complexity.

Answer 15

Is O(nlogn) in worst and average cases
Is O(n) in the best case for an array containing identical elements.

Question 16

Why do we like balanced trees?

Answer 16

Searches and insertions are most efficient when a binary tree is well balanced. O(log n)

Question 17

What is node balance?

Answer 17

Is the height of the right subtree minus theheight of the left subtree:

balance(n) = rightHeight(n)-leftHeight(n)
Where n is some node in the tree.

Question 18

What is an AVL tree?

Answer 18

Is an ordered binary tree where every node has a balance of -1 or 0 or +1.

Question 19

What is the general procedure for inserting into an AVL tree?

Answer 19

1. Insert the node into the tree, following the rules for a regular binary search tree.
2. If necessary, adjust the shape of the tree so that it conforms to the rules of an AVL tree.
3. Update the balance fields for all nodes affected by the steps above.

Question 20

In an AVL tree, what is a pivot node?

Answer 20

Is the ancestor node closest to the inserted node that is not in balance.

Question 21

What are the 3 different cases when inserting in an AVL tree?

Answer 21

1. There is no pivot
2. The pivot exists and you add the shorter subtree.
3. the pivot exists and you add the longer subtree.

Question 22

What do you do when you are inserting in an AVL tree with no pivot?

Answer 22

You are adding to a subtree with 0 balances.
So you change the balances for all ancestor nodes by + or - 1.

The shape of the tree is not adjusted after the insertion, but the balances must be updated.

Insert the node into its proper place in the tree.

Adjust the balances for all nodes from the inserted node up the root node.