To be a bit more precise: heaps are as cheap as arrays to search, both being O(log n). However, the a binary search on a circular buffer should have more overhead than a search through a heap, resulting in a larger constant on the estimate.
This page last modified on 24 January 2006.