This article was accepted into the corpus but its outbound wikilinks were never NER-processed — typical at the deepest BFS hop or when the run's entity cap was reached. No expansion funnel to show.
| Heap | |
|---|---|
| Name | Heap |
| Caption | Array-based binary heap visualization |
| Type | Data structure |
| Invented | 1964 |
| Inventor | J. W. J. Williams |
| Related | Priority queue; Binary tree; Fibonacci heap; Binomial heap |
Heap
A heap is an abstract data structure used to implement priority queue semantics, underpinning algorithms in Dijkstra's algorithm, Huffman coding, and Heapsort. It enforces an order property across a hierarchical arrangement to allow rapid access to extremal elements, and appears in software libraries in C++ Standard Library, Java Collections Framework, and Python (programming language) distributions. Heaps interact with algorithmic theory in venues such as ACM Symposium on Theory of Computing, SIAM Journal on Computing, and are central to courses at institutions like Massachusetts Institute of Technology and Stanford University.
A heap is defined by a structural invariant and an order invariant; common types include the binary heap introduced by J. W. J. Williams, the Fibonacci heap developed by Michael L. Fredman and Robert E. Tarjan, and the binomial heap described by Jean Vuillemin. Other named variants include the pairing heap (Amr Elmasry et al. research lineage), the radix heap used in monotone priority contexts, and the d-ary heap generalizing branching factor to d children. Heaps are classified as min-heaps or max-heaps depending on whether the root yields the minimum or maximum key, respectively; specialized forms include the implicit binary heap and the cache-aware van Emde Boas tree when combined with integer-key techniques.
Binary heaps are commonly implemented using a contiguous array mapping tree indices via parent and child formulas, as in implementations of std::priority_queue in ISO C++ and the heapq module in Python (programming language). Binomial heaps use a forest of binomial trees organized by degree and are often presented in textbooks from Knuth and courses at Princeton University. Fibonacci heaps rely on circular, doubly linked lists and consolidated degree trees as developed in papers published in Journal of the ACM; pairing heaps use linked-child sibling representations influenced by studies in ACM SIGPLAN Conference. Radix heaps and bucket-based implementations draw on integer domain properties in works associated with Dijkstra's algorithm optimizations and research at Eindhoven University of Technology.
Core operations include insert, find-min/find-max, extract-min/extract-max, decrease-key, merge (meld), and delete. Heapsort uses repeated extract-max or extract-min on a binary heap to produce a sorted sequence, a technique taught in CLRS and exhibited in courses at University of California, Berkeley. Decrease-key is efficient in Fibonacci heaps, which grant amortized bounds proven in analyses published in SIAM Journal on Computing and presented at ICALP proceedings. Meld operations are native to binomial and Fibonacci heaps, enabling priority queue union operations discussed in literature from Donald Knuth and conference papers at SODA.
Binary heaps provide O(log n) worst-case insert and extract operations and O(1) find-min, with space linear in n, as detailed in algorithm texts by Cormen, Leiserson, Rivest, and Stein and studies at MIT OpenCourseWare. Fibonacci heaps achieve amortized O(1) insert and decrease-key with amortized O(log n) extract-min, results established by Fredman and Tarjan in Journal of the ACM articles. Pairing heaps offer practical performance competitive with Fibonacci heaps per empirical studies at Google Research and academic benchmarks from University of Waterloo. Cache behavior and branch prediction effects have been examined in systems research from Intel and published in IEEE Transactions on Computers.
Heaps are integral to shortest-path algorithms like Dijkstra's algorithm and A* search, to compression schemes in Huffman coding, and to event scheduling in simulations as used by researchers at Los Alamos National Laboratory. Operating systems use heap-like structures for task scheduling in kernels such as Linux kernel and real-time systems described in work from IEEE Real-Time Systems Symposium. Databases and networking stack implementations in PostgreSQL and Apache HTTP Server employ priority queues for background tasks and request handling; heaps also support order-statistics in computational geometry libraries from CGAL and priority-based resource allocation in Amazon Web Services services.
Beyond classical variants, Fibonacci-heap derivatives such as the rank-pairing heap and theoretical structures like the strict Fibonacci heap explore constant-factor improvements, with research appearing in STOC and FOCS proceedings. External-memory and cache-oblivious heap designs arise in studies at Carnegie Mellon University and are applied in big-data frameworks like Hadoop and Apache Spark for priority-based task scheduling. Concurrent heaps, including lock-free priority queues and skiplist-based alternatives, are topics in publications from Microsoft Research and ETH Zurich. Specialized integer-key structures such as the van Emde Boas tree and radix heap support faster bounds under restricted domains, with influential work from Peter van Emde Boas and follow-on papers in Algorithmica.
Category:Data structures