A tree-shaped structure satisfying the heap property, that every parent is ordered relative to its children, so the minimum or maximum element is always at the root; the usual implementation behind a priority queue and behind heapsort.
Facts
Core PrincipleA complete tree where every node has a key more extreme (greater or less) than or equal to the key of its parent. Usually understood to be a binary heap. 2 Connections
Sources
1. Binary heap, Wikipedia
Lead sectionQuote, Lead section
The binary heap was introduced by J. W. J. Williams in 1964 as a data structure for implementing heapsort.
2. heap, Dictionary of Algorithms and Data Structures, NIST
DefinitionQuote, Definition
A complete tree where every node has a key more extreme (greater or less) than or equal to the key of its parent. Usually understood to be a binary heap.
Frequently Asked Questions
Who introduced the binary heap and why?
J. W. J. Williams introduced it in 1964 to implement heapsort.
The binary heap was introduced by J. W. J. Williams in 1964 as a data structure for implementing heapsort. It is a complete tree in which every node has a key more extreme than or equal to the key of its parent, and the term heap is usually understood to mean a binary heap.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.