Category: Heaps (data structures)

In computer science, a queap is a priority queue data structure. The data structure allows insertions and deletions of arbitrary elements, as well as retrieval of the highest-priority element. Each de
Binomial heap
In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged.It is important as an implementation of the mergeable heap abstract d
D-ary heap
The d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2. Thus, a binary heap is a 2-heap, and a ternary heap is
Shadow heap
In computer science, a shadow heap is a mergeable heap data structure which supports efficient heap merging in the amortized sense. More specifically, shadow heaps make use of the shadow merge algorit
Kinetic hanger
A Kinetic hanger is a randomized version of a kinetic heap whose performance is easy to analyze tightly. A kinetic hanger satisfies the heap property (the priority of each element is higher than the p
K-D heap
A K-D heap is a data structure in computer science which implements a multidimensional priority queue without requiring additional space. It is a generalization of the Heap. It allows for efficient in
Min-max heap
In computer science, a min-max heap is a complete binary tree data structure which combines the usefulness of both a min-heap and a max-heap, that is, it provides constant time retrieval and logarithm
Binary heap
A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964,
Addressable heap
In computer science, an addressable heap is an abstract data type. Specifically, it is a mergeable heap supporting access to the elements of the heap via handles (also called references). It allows th
Skew binomial heap
In computer science, a skew binomial heap (or skew binomial queue) is a variant of the binomial heap that supports constant-time insertion operations in the worst case, rather than the logarithmic wor
In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an un
Pairing heap
A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, an
In computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algor
Brodal queue
In computer science, the Brodal queue is a heap/priority queue structure with very low worst case time bounds: for insertion, find-minimum, meld (merge two queues) and decrease-key and for delete-mini
Adaptive heap sort
In computer science, adaptive heap sort is a comparison-based sorting algorithm of the adaptive sort family. It is a variant of heap sort that performs better when the data contains existing order. Pu
Kinetic heap
A Kinetic Heap is a kinetic data structure, obtained by the kinetization of a heap. It is designed to store elements (keys associated with priorities) where the priority is changing as a continuous fu
Leftist tree
In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s-value which is the distance to the nearest leaf in subtree ro
A beap, or bi-parental heap, is a data structure where a node usually has two parents (unless it is the first or last on a level) and two children (unless it is on the last level). Unlike a heap, a be
Fibonacci heap
In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priori
A B-heap is a binary heap implemented to keep subtrees in a single page. This reduces the number of pages accessed by up to a factor of ten for big heaps when using virtual memory, compared with the t
Mergeable heap
In computer science, a mergeable heap (also called a meldable heap) is an abstract data type, which is a heap supporting a merge operation.
2–3 heap
In computer science, a 2–3 heap is a data structure, a variation on the heap, designed by in 1999. The structure is similar to the Fibonacci heap, and borrows from the 2–3 tree. Time costs for some co
Radix heap
A radix heap is a data structure for realizing the operations of a monotone priority queue. A set of elements to which a key is assigned can then be managed. The run time of the operations depends on
In computer science, the AF-heap is a type of priority queue for integer data, an extension of the fusion tree using an proposed by M. L. Fredman and D. E. Willard. Using an AF-heap, it is possible to
In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary se
Heap (data structure)
In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a par
Skew heap
A skew heap (or self-adjusting heap) is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps. In contrast wi
Kinetic heater
A Kinetic Heater is a kinetic priority queue similar to a kinetic heap, that makes use of randomization to simplify its analysis in a way similar to a treap. Specifically, each element has a random ke
Double-ended priority queue
In computer science, a double-ended priority queue (DEPQ) or double-ended heap is a data structure similar to a priority queue or heap, but allows for efficient removal of both the maximum and minimum
Soft heap
In computer science, a soft heap is a variant on the simple heap data structure that has constant amortized time complexity for 5 types of operations. This is achieved by carefully "corrupting" (incre
Weak heap
In computer science, a weak heap is a data structure for priority queues, combining features of the binary heap and binomial heap. It can be stored in an array as an implicit binary tree like a binary