Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Soft_heap> ?p ?o }
Showing triples 1 to 40 of
40
with 100 triples per page.
- Soft_heap abstract "In computer science, a soft heap is a variant on the simple heap data structure that has constant amortized time for 5 types of operations. This is achieved by carefully "corrupting" (increasing) the keys of at most a certain number of values in the heap. The constant time operations are: create(S): Create a new soft heap insert(S, x): Insert an element into a soft heap meld(S, S' ): Combine the contents of two soft heaps into one, destroying both delete(S, x): Delete an element from a soft heap findmin(S): Get the element with minimum key in the soft heapOther heaps such as Fibonacci heaps achieve most of these bounds without any corruption, but cannot provide a constant-time bound on the critical delete operation. The amount of corruption can be controlled by the choice of a parameter ε, but the lower this is set, the more time insertions require (O(log 1/ε) for an error rate of ε).More precisely, the guarantee offered by the soft heap is the following: for a fixed value ε between 0 and 1/2, at any point in time there will be at most ε*n corrupted keys in the heap, where n is the number of elements inserted so far. Note that this does not guarantee that only a fixed percentage of the keys currently in the heap are corrupted: in an unlucky sequence of insertions and deletions, it can happen that all elements in the heap will have corrupted keys. Similarly, we have no guarantee that in a sequence of elements extracted from the heap with findmin and delete, only a fixed percentage will have corrupted keys: in an unlucky scenario only corrupted elements are extracted from the heap.The soft heap was designed by Bernard Chazelle in 2000. The term "corruption" in the structure is the result of what Chazelle called "carpooling" in a soft heap. Each node in the soft heap contains a linked-list of keys and one common key. The common key is an upper bound on the values of the keys in the linked-list. Once a key is added to the linked-list, it is considered corrupted because its value is never again relevant in any of the soft heap operations: only the common keys are compared. This is what makes soft heaps "soft"; you can't be sure whether or not any particular value you put into it will be corrupted. The purpose of these corruptions is effectively to lower the information entropy of the data, enabling the data structure to break through information-theoretic barriers regarding heaps.".
- Soft_heap wikiPageExternalLink summary?doi=10.1.1.5.9705.
- Soft_heap wikiPageExternalLink 1.9781611973068.53.
- Soft_heap wikiPageID "546678".
- Soft_heap wikiPageLength "6265".
- Soft_heap wikiPageOutDegree "17".
- Soft_heap wikiPageRevisionID "666581987".
- Soft_heap wikiPageWikiLink Amortized_analysis.
- Soft_heap wikiPageWikiLink Bernard_Chazelle.
- Soft_heap wikiPageWikiLink Big-O_notation.
- Soft_heap wikiPageWikiLink Big_O_notation.
- Soft_heap wikiPageWikiLink Canterbury_scene.
- Soft_heap wikiPageWikiLink Category:Heaps_(data_structures).
- Soft_heap wikiPageWikiLink Computer_science.
- Soft_heap wikiPageWikiLink Data_structure.
- Soft_heap wikiPageWikiLink Entropy_(information_theory).
- Soft_heap wikiPageWikiLink Fibonacci_heap.
- Soft_heap wikiPageWikiLink Heap_(data_structure).
- Soft_heap wikiPageWikiLink Information_entropy.
- Soft_heap wikiPageWikiLink Information_theory.
- Soft_heap wikiPageWikiLink Insertion_sort.
- Soft_heap wikiPageWikiLink Master_theorem.
- Soft_heap wikiPageWikiLink Minimum_spanning_tree.
- Soft_heap wikiPageWikiLink Quicksort.
- Soft_heap wikiPageWikiLink Selection_algorithm.
- Soft_heap wikiPageWikiLinkText "Soft heap".
- Soft_heap wikiPageWikiLinkText "soft heap".
- Soft_heap hasPhotoCollection Soft_heap.
- Soft_heap wikiPageUsesTemplate Template:For.
- Soft_heap subject Category:Heaps_(data_structures).
- Soft_heap hypernym Variant.
- Soft_heap comment "In computer science, a soft heap is a variant on the simple heap data structure that has constant amortized time for 5 types of operations. This is achieved by carefully "corrupting" (increasing) the keys of at most a certain number of values in the heap.".
- Soft_heap label "Soft heap".
- Soft_heap sameAs Montículo_suave.
- Soft_heap sameAs m.02nr7v.
- Soft_heap sameAs Soft_hip.
- Soft_heap sameAs Q7553986.
- Soft_heap sameAs Q7553986.
- Soft_heap wasDerivedFrom Soft_heap?oldid=666581987.
- Soft_heap isPrimaryTopicOf Soft_heap.