function concurrent_delete(heap: heap_t)

      // Grab an item from the bottom of the heap to replace the
      //   to-be-deleted top item.

      print Thead id and "deleteMax getting heapLock"

      lock(heap.lock)
      bottom := bit_reversed_decrement(heap.size)
      LOCK(bottom)
      unlock(heap.lock)
      priority := PRIORITY(bottom)
      TAG(bottom) := EMPTY
      UNLOCK(bottom)

      // Lock first item.  Stop if it was the only item in the heap.
      LOCK(1)
      if TAG(1) = EMPTY then
          UNLOCK(1)
          return priority
      endif

      // Replace the top item with the item stored from the bottom.
      swap(priority, PRIORITY(1))    // 'priority' used for return value, later
      TAG(1) := AVAILABLE

      // Adjust the heap starting at the top.
      //   We always hold a lock on the item being adjusted.
      i := 1
      while (i < MAX_SIZE / 2) do
          left := i * 2
          right := i * 2 + 1

          print Thead id, i and "deleteMax getting itemLocks"

          LOCK(left)
          LOCK(right)

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

          if TAG(left) = EMPTY then
              UNLOCK(right)
              UNLOCK(left)
              break
          else if TAG(right) = EMPTY or PRIORITY(left) > PRIORITY(right) then
              UNLOCK(right)
              child := left
          else
              UNLOCK(left)
              child := right
          endif

          // If the child has a higher priority than the parent then
          //   swap them.  If not, stop.
          if PRIORITY(child) > PRIORITY(i) then
              swap_items(child, i)   // swap priority and tag, not itemLock
              UNLOCK(i)
              i := child
          else
              UNLOCK(child)
              break
          endif
      enddo
      UNLOCK(i)
      return priority
  end