DecreaseKeys are expensive for external memory priority queues.

Kasper Eenberg, Kasper Green Larsen, Huacheng Yu

Browse the full STOC paper archive.