A Heap is a data structure that provides an efficent implementation of priority queue operations. That is, it provides a - first in largest out - queue, according to some ordering relation. In more detail, a priority queue provides at least the following queue operations
This minimal set of primitives are often extended by an AdjustKey operation which adjusts the key of an element already in the queue, and a non desctructive version of ExtractMax which returns the largest element in the queue without removing it from the queue.