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.

Pages: 1 2

6 Responses to “Conditional Heap Insertion”

  1. Paul said

    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.

    from heapq import heappush
    def cond_heappush(heap, item):
        if item not in heap:
            heappush(heap, item)
    
  2. Perl…. a simple OO version

    my @ids = qw(12 5 13 3 5 9 6 4 9 3 1 44);
    
    my $x = Heap->new;
    $x->push( $_ ) foreach @ids;
    print join ", ", $x->dump,"\n";
    
    package Heap;
    
    sub new {
      my $self = [];
      bless $self;
      return $self;
    }
    
    sub push {
      my ( $self,$v )  = @_;
      unless( @{$self} )  {
        push @{$self}, $v,Heap->new,Heap->new unless @{$self};
        return $self;
      }
      return $self if $self->[0] == $v;
      $self->[ $v < $self->[0] ? 1 : 2 ]->push( $v );
      return $self;
    }
    
    sub dump {
      my $self = shift;
      return unless @{$self};
      return ($self->[1]->dump,$self->[0],$self->[2]->dump);
    }
    
    1;
    
    
  3. John Cowan said

    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.

  4. Josh said

    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.

  5. Daniel said

    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”

    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    /*
     * Array-Backed Heap
     */
    
    // TODO: A function for removing the root (reheapification downward),
    // int HeapRemove(Heap* h);
    // It wasn't necessary for the problem you were working on.
    
    // TODO: A function for building a heap from an arbitrary list of elements,
    // void HeapBuild(Heap* h, int* elements, int count);
    // There is an O(n) way to do this, versus calling HeapInsert n times,
    // which is O(n log n).
    
    // Helpers
    
    typedef int bool;
    #define true 1
    #define false 0
    
    // Given the index of a node in a binary tree, return the parent index.
    // Returns -1 if node_index is the root node.
    int parent(int node_index) {
      assert(node_index >= 0);  // 0 is the root
      return (node_index-1) >> 1;  // floor((node_index-1)/2)
    }
    
    void terpri(int count) {
      for (int i = 0; i < count; i++) {
        printf("\n");
      }
    }
    
    // Data structures
    
    typedef struct {
      int* array;
      int count;
      int capacity;
    } Heap;
    
    // Initialize an empty heap.
    void HeapInit(Heap* h, int capacity) {
      assert(capacity > 0);
      h->count = 0;
      h->capacity = capacity;
      h->array = malloc(sizeof(int) * capacity);
    }
    
    void HeapCleanup(Heap* h) {
      free(h->array);
    }
    
    // O(log n)
    void HeapInsert(Heap* h, int element) {
      if (h->capacity <= h->count) {
        // Alternatively could realloc
        fprintf(stderr, "Heap full (%d elements)\n", h->capacity);
        abort();
      }
    
      int* array = h->array;
    
      array[h->count] = element;
    
      int index = h->count;
      int parent_index = parent(index);
    
      while (parent_index >= 0 &&
          array[index] > array[parent_index]) {
    
        // swap
        int tmp = array[index];
        array[index] = array[parent_index];
        array[parent_index] = tmp;
    
        index = parent_index;
        parent_index = parent(index);
      }
    
      h->count++;
    }
    
    bool HeapContains(Heap* h, int element) {
      // TODO: Can return early if an entire level of the corresponding binary tree
      // is less than element.
      for (int i = 0; i < h->count; i++) {
        if (h->array[i] == element) {
          return true;
        }
      }
      return false;
    }
    
    // Inserts an element if it's not present (hence "New").
    // Returns false iff item was already in the heap.
    bool HeapInsertNew(Heap* h, int element) {
      bool contained = HeapContains(h, element);
      if (!contained) {
        HeapInsert(h, element);
      }
      return !contained;
    }
    
    void HeapPrint(Heap* h) {
      for (int i = 0; i < h->count; i++) {
        printf("%d ", h->array[i]);
      }
    }
    
    int main(int argc, char* argv[]) {
      Heap h;
      HeapInit(&h, 100);
    
      int elements[] = {77, 5, 33, 29, 16, 9, 82};
      int n = sizeof(elements) / sizeof(elements[0]);
      for (int i = 0; i < n; i++) {
        HeapInsert(&h, elements[i]);
      }
    
      printf("Original Heap\n");
      HeapPrint(&h);
      terpri(2);
    
      printf("Insert 29 (an existing element) with HeapInsertNew\n");
      HeapInsertNew(&h, 29);
      HeapPrint(&h);
      terpri(2);
    
      printf("Insert 30 (a new element) with HeapInsertNew\n");
      HeapInsertNew(&h, 30);
      HeapPrint(&h);
      terpri(1);
    
      HeapCleanup(&h);
    
      return 0;
    }
    
  6. Daniel said

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

    Original Heap
    82 29 77 5 16 9 33 
    
    Insert 29 (an existing element) with HeapInsertNew
    82 29 77 5 16 9 33 
    
    Insert 30 (a new element) with HeapInsertNew
    82 30 77 29 16 9 33 5 
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: