|
Meldable 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 * Fib ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, applied disciplines (including the design and implementation of Computer architecture, hardware and Software engineering, software). 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 preventing security vulnerabilities. Computer graphics (computer science), Computer graphics and computational geometry address the generation of images. Programming language theory considers different ways to describe computational processes, and database theory concerns the management of re ... [...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, defined by its behavior (semantics) from the point of view of a '' 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. For example, a stack has push/pop operations that follow a Last-In-First-Out rule, and can be concretely implemented using either a list or an array. Another example is a set which stores values, without any particular order, and no repeated values. Values themselves are not retrieved from sets; rather, one tests a value for membership to obtain a Boolean "in" or "not in". ADTs are a theoretical concept, used in formal semantics and program verification and, less strictly, in the design and analysis of algorithms, data structu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Heap (data Structure)
In computer science, a heap is a Tree (data structure), tree-based data structure that satisfies the heap property: In a ''max heap'', for any given Node (computer science), node C, if P is the 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 interspersed wit ... [...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. It is an example of a mergeable heap (also called meldable heap), as it supports merging two heaps in logarithmic time. It is implemented as a Heap (data structure), 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 tree data structure, 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 order k has \tbinom k d nodes at depth d, a ... [...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. The amortized times of all operations on Fibonacci heaps is constant, except ''delete-min''. 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-min'' operations would take O(a + b\log n) worst case time, where n is the maximum heap size. In a binary 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 in subtree rooted at x. In contrast to a ''binary heap'', a leftist tree attempts to be very unbalanced. In addition to the 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 O(log ''n'') worst-case. Left ... [...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 \va ... [...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] |
