A heap is a tree-based data structure that maintains the heap property: every parent node compares as smaller than or equal to its children (a min-heap) or larger than or equal to them (a max-heap). This property does not fully sort the data, but it guarantees that the minimum or maximum element sits at the root, where it can be read immediately.
The binary heap was introduced by J. W. J. Williams in 1964 in “Algorithm 232: Heapsort,” published in Communications of the ACM, volume 7, issue 6, pages 347 to 348. Williams’ design stores the heap as a complete binary tree packed into an array, so a node at a given position can find its parent and children by simple index arithmetic rather than explicit pointers. Knuth later treats heaps and heapsort as part of the systematic study of sorting in The Art of Computer Programming.
Insertion and removal of the root each take time proportional to log n, because after the structure is changed the heap property is restored by “sifting” an element up or down along a single path from leaf to root or root to leaf. Reading the minimum or maximum, by contrast, is immediate, since it is always at the root.
These properties make the heap the standard implementation of a priority queue, where elements are served in order of priority rather than arrival. The same structure also drives heapsort, which builds a heap from the input and then repeatedly extracts the root to produce a sorted sequence in place.