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, where n is 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.
Programming Praxis 