## Conditional Heap Insertion

### May 17, 2016

This is an Amazon interview question:

Given a heap (priority queue), insert an element into the heap if the element is not already present in the heap. Your solution must work in O(

n) time, wherenis the number of items in the heap.

Your task is to write a program to insert an element into a heap if the element is not already present in the heap, in logarithmic time. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

In Python this is easy. Heaps are implemented as lists, so it is easy to see if the new item is in the heap. If not, use heappush to insert the item in the heap.

Perl…. a simple OO version

The question as posed by Amazon is bizarre. If you are willing to pay the price of O(n) insertion time, you might as well use a linked list instead of a heap.

I would use an additional set to store elements that are in the heap. This requires extra space, but doesn’t alter Big Oh times.

Here’s a solution in C. I used an array-backed heap, where the array represents a binary tree (index 0 is the root, 1 and 2 are the children of the root, and e.g., 9 and 10 are the children of node 4).

I did not implement reheapification downward, which wasn’t necessary for this problem (since there is no removal from the heap).

Also note, the amazon question, as written on this page, says O(n), but the following text after the quote says “in logarithmic time”. The solution page implies that the amazon question is a trick question, but it’s seemingly the programming praxis portion that is a trick question (assuming the amazon quote is correct).

Also, I believe there are some issues on the solution page:

> “It is not possible to perform the task in O(n) time.”

should seemingly say “O(log n) time”

> “Once you know the element is not in the heap, it can be inserted in O(n) time”

should seemingly say “inserted in O(log n) time”

I forgot to include the program output. Here it is. Also, HeapInsertNew is the function corresponding to the question.