EPI - 10.6 - Almost sorted sequence, output in sorted order

Each element is perturbed by k, where k is not known a-prioi (the
book assumes that k is known a-prioi). Come up with a O(k) space
solution for outputting the sequence in-order using a min-heap.