A bi-pri queue is a fast priority queue that supports random insertion and popping from either end.
However, the design as originally posted on this page was unnecessarily paranoid. It said that when a value is floated upward into a heap, it may have to sink down again, because it floats up through one branch, and wasn't compared with its new child node from the other branch. But it was compared to the child's previous parent, so obviously the new node, which has just been placed above the old parent, must also belong above the other child. Please feel free to ridicule me mercilessly, because that was a really dumb oversight.
Also, there's already an equivalent data structure called the interval heap. Thanks to kinguy on reddit.com for mentioning that. I may update the Lisp implementation one of these days, but it's not currently a high priority.