Lesson plan

beap

A beap, or bi-parental heap, is a data structure for a set (or map, or multiset or multimap) that enables elements (or mappings) to be located, inserted, or deleted in sublinear time. In a beap, each element is stored in a node with up to two parents and up to two children, with the property that the value of a parent node is never greater than the value of either of its children. Beaps are implemented using an array containing only the values to be stored, with the parent-child relationships being determined implicitly by the array indices. (That is: beaps are an implicit data structure.) In that respect they are similar to binary heaps, which are usually implemented that way as well. However, their performance characteristics are different from heaps; in particular, a beap enables sublinear retrieval of arbitrary elements. The beap was introduced by Ian Munro and Hendra Suwanda. A related data structure is the Young tableau.

Back to article

Article summary

A beap, or bi-parental heap, is a data structure for a set (or map, or multiset or multimap) that enables elements (or mappings) to be located, inserted, or deleted in sublinear time. In a beap, each element is stored in a node with up to two parents and up to two children, with the property that the value of a parent node is never greater than the value of either of its children. Beaps are implemented using an array containing only the values to be stored, with the parent-child relationships being determined implicitly by the array indices. (That is: beaps are an implicit data structure.) In that respect they are similar to binary heaps, which are usually implemented that way as well. However, their performance characteristics are different from heaps; in particular, a beap enables sublinear retrieval of arbitrary elements. The beap was introduced by Ian Munro and Hendra Suwanda. A related data structure is the Young tableau.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.