Priority Queues in CL

There is a new CDR by Ingvar Mattsson proposing the specification of a simple heap (priority queue) interface for CL: CDR 12: Generic extendable heaps for Common Lisp.
The question in this case is how to support the INCREASE-KEY (or DECREASE-KEY) operation mentioned by CLRS.  It is known that such support is application-dependent, however, it would be nice to make it explicit.
Just to show my age, about 20 years ago, I did write a priority queue implementation that is still available in the CMU AI Repository.  In that ancient implementation, a hash table was used internally to support the INCREASE-KEY/DECREASE-KEY operation and I always wondered whether there is a better interface to aid the maintenance of the heap invariants while keeping the performance guarantees.
Any suggestions?