What is a heap and when should you use it in coding interviews?

A heap is a complete binary tree satisfying the heap property: in a min-heap every parent is smaller than its children, in a max-heap every parent is larger. Heaps support insertion and extraction of the minimum or maximum element in O of log n time, and peeking at the top in O of one. Use a heap when the problem asks for the k largest or smallest elements, when you need to repeatedly access the extreme value, or when you need to merge k sorted sequences. Building a heap from n elements takes O of n time.