procedure concurrent_insert(priority, heap: heap_t)

      // Insert new item at bottom of the heap.
      lock(heap.lock)
      i := bit_reversed_increment(heap.size)

      print Thread id and priority to be inserted

      LOCK(i)
      unlock(heap.lock)
      PRIORITY(i) := priority
      TAG(i) := pid
      UNLOCK(i)

      // Move item towards top of heap while it has a higher priority
      //   than its parent.
      while i > 1 do

          print Thread id, i and "getting itemLocks"

          parent := i / 2
          LOCK(parent)
          LOCK(i)
          old_i := i

          // add call to Thread.sleep() here, if needed

          if TAG(parent) = AVAILABLE and TAG(i) = pid then

              print Thread id, i and "parent available"
              if PRIORITY(i) > PRIORITY(parent) then
                  swap_items(i, parent)   // swap priority and tag, not itemLock
                  i := parent
              else
                  TAG(i) := AVAILABLE
                  i := 0
              endif

          else if TAG(parent) = EMPTY then

              print Thread id, i and "parent empty"
              i := 0

          else if TAG(i) != pid then

              print Thread id, i and "not my ID"
              i := parent

          else 

             print Thread id, i and "parent not avaliable"
             // do nothing otherwise

          endif

          UNLOCK(old_i)
          UNLOCK(parent)
      enddo


      if i = 1 then
          LOCK(i)
          if TAG(i) = pid then
              TAG(i) := AVAILABLE
          endif
          UNLOCK(i)
      endif

  end  // of procedure