This paper presents a binary search algorithm on the path of a heap. If a heap is used to realize priority queue, logn+a3(n) + 1 comparisons are sufficient to replace the maximum element in the heap by the algorithm.