Using min-max heaps should be workable; indeed, the resulting data structure seems to be a special case of the data structure described in section 3 of [1].<p>[1] <a href="http:&#x2F;&#x2F;www.cs.otago.ac.nz&#x2F;staffpriv&#x2F;mike&#x2F;Papers&#x2F;MinMaxHeaps&#x2F;MinMaxHeaps.pdf" rel="nofollow">http:&#x2F;&#x2F;www.cs.otago.ac.nz&#x2F;staffpriv&#x2F;mike&#x2F;Papers&#x2F;MinMaxHeaps&#x2F;...</a>