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" (increasing) the keys of at most a constant 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 heap
| Attributes | Values |
|---|
| rdfs:label
| - Montículo suave (es)
- Soft heap (en)
|
| rdfs:comment
| - En computación, un montículo suave (soft heap en inglés) es una variante de la estructura de datos montículo. Fue concebida por Bernard Chazelle en el año 2000. Al corromper (aumentar) cuidadosamente las claves de a lo sumo un cierto porcentaje fijo de valores en el montículo, logra obtener acceso en amortizado para sus cuatro operaciones: (es)
- 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" (increasing) the keys of at most a constant 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 heap (en)
|
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - En computación, un montículo suave (soft heap en inglés) es una variante de la estructura de datos montículo. Fue concebida por Bernard Chazelle en el año 2000. Al corromper (aumentar) cuidadosamente las claves de a lo sumo un cierto porcentaje fijo de valores en el montículo, logra obtener acceso en amortizado para sus cuatro operaciones:
* create(S): Create un nuevo montículo suave
* insert(S, x): Inserta un elemento en un montículo suave
* meld(S, S' ): Combina el contenido de dos montículo suaves en uno. Ambos parámetros son destruidos en el proceso
* delete(S, x): Borra un elemento de un montículo suave
* findmin(S): Obtiene el elemento de clave mínima en el montículo suave Otros montículos como el montículo de Fibonacci logran este tipo de cota para algunas operaciones sin necesidad de corromper las claves, sin embargo, no logran acotar de forma constante la crítica operación delete. El porcentaje de valores que son modificados puede ser escogido libremente, pero mientras más bajo sea, más tiempo requieren las inserciones (O(log 1/ε) para una tasa de ε). Las corrupciones bajan efectivamente la entropía de información. (es)
- 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" (increasing) the keys of at most a constant 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 heap Other 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. (en)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)