Amazon Preparation

Question 1

What is a priority queue?

Answer 1

Is a data structure that holds elements in order.
You can:
Insert a new element
Remove the max in a MaxHeap

Question 2

How do you implement a priority queue?

Answer 2

The best implementation uses a heap.

The heap is a complete binary tree with the invariant that all child nodes will be greater or smaller than the parent node.

We can use an array to implement this binary tree. Starting at index 1 we can use index arithmetic to go child nodes or to move up the tree. If a node is at index i, his childs are going to be at i2 and i2+1. If a node is at index j his father will be at index j/2. We also need to be aware of running out of array bounds when traversing the binary tree represented using an array.

Question 3

What is a heap?

Answer 3

A heap is a complete binary tree that has the invariant that all children nodes of a node N will be either greater (in a min heap) or smaller (in a max heap) than the value of node N.

Question 4

How do you implement the insert operation in a priority queue using a heap?

Answer 4

You insert the element at the end of the array and apply the swim operation.

The swim operation compares the elements with its father and if the comparison violates the heap invariant we exchange both elements move up to the father and execute the operation again.

Insertion takes O(log n) because the maximum number of operations would be equal to the height of the tree, that is log n.

Question 5

How do you implement the delete_max or delete_min operation in a priority queue using a heap?

Answer 5

You save the root in a temporary variable.
Exchange the root with the last element.
Reduce the size of the heap and execute the sink operation on the root.

The sink operation takes the element and compares with its child.
If there is a violation of the heap invariant we exchange the parent with the greatest, or smallest child, depending on which invariant we wanna hold.
After the swap, we move down and execute the sink operation again.

This operation takes O(log n) because the number of operations is proportional to the tree height.

Question 6

What are simpler implementations of a priority queue? (not using a heap)

Answer 6

We can implement a priority queue using an unordered array, but deleting the max would take O(N). Inserting would take O(1)

Or we could implement with an ordered array, but insertion would take O(N) (to move N elements after insertion), and deleting the max would be constant.