|
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. Definition A mergeable heap supports the usual heap operations: * Make-Heap(), create an empty heap. * Insert(H,x), insert an element x into the heap H. * Min(H), return the minimum element, or Nil if no such element exists. * Extract-Min(H), extract and return the minimum element, or Nil if no such element exists. And one more that distinguishes it: * Merge(H1,H2), combine the elements of H1 and H2 into a single heap. Trivial implementation It is straightforward to implement a mergeable heap given a simple heap: Merge(H1,H2): # x ← Extract-Min(H2) # while x ≠ Nil ## Insert(H1, x) ## x ← Extract-Min(H2) This can however be wasteful as each Extract-Min(H) and Insert(H,x) typically have to maintain the heap property. More efficient implementations Examples of mergeable heap data structures include: * Binomial heap * Fibo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical disciplines (including the design and implementation of Computer architecture, hardware and Computer programming, software). Computer science is generally considered an area of research, academic research and distinct from computer programming. Algorithms and data structures are central to computer science. The theory of computation concerns abstract models of computation and general classes of computational problem, problems that can be solved using them. The fields of cryptography and computer security involve studying the means for secure communication and for preventing Vulnerability (computing), security vulnerabilities. Computer graphics (computer science), Computer graphics and computational geometry address the generation of images. Progr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Abstract Data Type
In computer science, an abstract data type (ADT) is a mathematical model for data types. An abstract data type is defined by its behavior (Semantics (computer science), semantics) from the point of view of a ''User (computing), user'', of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This mathematical model contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user. Formally, an ADT may be defined as a "class of objects whose logical behavior is defined by a set of values and a set of operations"; this is analogous to an algebraic structure in mathematics. What is meant by "behaviour" varies by author, with the two main types of formal specifications for behavior being ''axiomatic (algebraic) specification'' and an ''abstract model;'' these correspond to axiomatic semantics and operational semantics of an abstract machine, r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 parent node of C, then the ''key'' (the ''value'') of P is greater than or equal to the key of C. In a ''min heap'', the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the ''root'' node. The heap is one maximally efficient implementation of an abstract data type called a priority queue, and in fact, priority queues are often referred to as "heaps", regardless of how they may be implemented. In a heap, the highest (or lowest) priority element is always stored at the root. However, a heap is not a sorted structure; it can be regarded as being partially ordered. A heap is a useful data structure when it is necessary to repeatedly remove the object with the highest (or lowest) priority, or when insertions need to be inters ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 data type (also called meldable heap), which is a priority queue supporting merge operation. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin. Binomial heap A binomial heap is implemented as a set of binomial trees (compare with a binary heap, which has a shape of a single binary tree), which are defined recursively as follows: * A binomial tree of order 0 is a single node * A binomial tree of order k has a root node whose children are roots of binomial trees of orders k-1, k-2, ..., 2, 1, 0 (in this order). A binomial tree of order k has 2^k nodes, and height k. The name comes from the shape: a binomial tree of ord ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 priority queue data structures including the binary heap and binomial heap. Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987. Fibonacci heaps are named after the Fibonacci numbers, which are used in their running time analysis. For the Fibonacci heap, the find-minimum operation takes constant ('' O''(1)) amortized time. The insert and decrease key operations also work in constant amortized time. Deleting an element (most often used in the special case of deleting the minimum element) works in ''O''(log ''n'') amortized time, where ''n'' is the size of the heap. This means that starting from an empty data structure, any sequence of ''a'' insert and decrease key operations and ''b'' delete operations would take ''O ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 node, leaf in subtree rooted at x. In contrast to a ''binary heap'', a leftist tree attempts to be very unbalanced. In addition to the heap (data structure), heap property, leftist trees are maintained so the right descendant of each node has the lower s-value. The height-biased leftist tree was invented by Clark Allan Crane. The name comes from the fact that the left subtree is usually taller than the right subtree. A leftist tree is a mergeable heap. When inserting a new node into a tree, a new one-node tree is created and merged into the existing tree. To delete an item, it is replaced by the merge of its left and right sub-trees. Both these operations take O(log ''n'') time. For insertions, this is slower than Fibonacci heaps, which support insertion in O(1) (constant) amortized time, and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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, and Robert Tarjan in 1986. Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm, and support the following operations (assuming a min-heap): * ''find-min'': simply return the top element of the heap. * ''meld'': compare the two root elements, the smaller remains the root of the result, the larger element and its subtree is appended as a child of this root. * ''insert'': create a new heap for the inserted element and ''meld'' into the original heap. * ''decrease-key'' (optional): remove the subtree rooted at the key to be decreased, replace the key with a smaller key, then ''meld'' the result back into the heap. * ''delete-min'': remove ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 with binary heaps, there are no structural constraints, so there is no guarantee that the height of the tree is logarithmic. Only two conditions must be satisfied: * The general heap order must be enforced * Every operation (add, remove_min, merge) on two skew heaps must be done using a special ''skew heap merge''. A skew heap is a self-adjusting form of a leftist heap which attempts to maintain balance by unconditionally swapping all nodes in the merge path when merging two heaps. (The merge operation is also used when adding and removing values.) With no structural constraints, it may seem that a skew heap would be horribly inefficient. However, amortized complexity analysis can be used to demonstrate that all operations on a skew heap can be done in O(log ''n''). In fact, with \varph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 the key of the element referenced by a particular handle to be removed or decreased. Definition An addressable heap supports the following operations: * Make-Heap(), creating an empty heap. * Insert(H,x), inserting an element x into the heap H, and returning a handle to it. * Min(H), returning a handle to the minimum element, or Nil if no such element exists. * Extract-Min(H), extracting and returning a handle to the minimum element, or Nil if no such element exists. * Remove(h), removing the element referenced by h (from its respective heap). * Decrease-Key(h,k), decreasing the key of the element referenced by h to k; illegal if k is larger than the key referenced by h. * Merge(H1,H2), combining the elements of H1 and H2. Examples Examples of addressable heaps include: * Fibona ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
