### Abstract

A simple variant of a priority queue, called a soft heap, is introduced. The data structure supports the usual operations: insert, delete, meld, and findmin. In order to beat the standard information-theoretic bounds, the soft heap allows errors: occasionally, the keys of certain items are artificially raised. Given any 0 < ε < 1/2 and any mixed sequence of n operations, the soft heap ensures that at most εn keys are raised at any time. The amortized complexity of each operation is constant, except for insert, which takes O(log 1/ε) time. The soft heap is optimal. Also, being purely pointer-based, no arrays are used and no numeric assumptions are made on the keys. The novelty of the data structure is that items are moved together in groups, in a data-structuring equivalent of "car pooling." The main application of the data structure is a faster deterministic algorithm for minimum spanning trees.

Original language | English (US) |
---|---|

Title of host publication | Algorithms, ESA 1998 - 6th Annual European Symposium, Proceedings |

Publisher | Springer Verlag |

Pages | 35-42 |

Number of pages | 8 |

ISBN (Print) | 3540648488, 9783540648482 |

DOIs | |

State | Published - 1998 |

Event | 6th Annual European Symposium on Algorithms, ESA 1998 - Venice, Italy Duration: Aug 24 1998 → Aug 26 1998 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1461 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 6th Annual European Symposium on Algorithms, ESA 1998 |
---|---|

Country | Italy |

City | Venice |

Period | 8/24/98 → 8/26/98 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Car-pooling as a data structuring device: The soft heap'. Together they form a unique fingerprint.

## Cite this

*Algorithms, ESA 1998 - 6th Annual European Symposium, Proceedings*(pp. 35-42). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1461 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-68530-8_3