“Beap”的意思、由来-开放百科全书

词条

Beap

释义

Performance
References

A beap, or bi-parental heap, is a data structure where a node usually has two parents (unless it is the first or last on a level) and two children (unless it is on the last level). Unlike a heap, a beap allows sublinear search. The beap was introduced by Ian Munro and Hendra Suwanda. A related data structure is the Young tableau.

Performance

The height of the structure is approximately . Also, assuming the last level is full, the number of elements on that level is also . In fact, because of these properties all basic operations (insert, remove, find) run in time on average. Find operations in the heap can be in the worst case. Removal and insertion of new elements involves propagation of elements up or down (much like in a heap) in order to restore the beap invariant. An additional perk is that beap provides constant time access to the smallest element and time for the maximum element.

Actually, a find operation can be implemented if parent pointers at each node are maintained. You would start at the absolute bottom-most element of the top node (similar to the left-most child in a heap) and move either up or right to find the element of interest.

References

{{cite journal | last1 = Munro | first1 = J. Ian | last2 = Suwanda | first2 = Hendra | year = 1980 | title = Implicit data structures for fast search and update | url = http://www.sciencedirect.com/science/article/pii/0022000080900379 | journal = Journal of Computer and System Sciences | volume = 21 | issue = 2| pages = 236–250 | doi=10.1016/0022-0000(80)90037-9}}
{{cite journal |first=J. W. J. |last=Williams |author-link=J. W. J. Williams |title=Algorithm 232 - Heapsort |date=Jun 1964 |journal=Communications of the ACM |volume=7 |issue=6 |pages=347–348 | doi = 10.1145/512274.512284}}

1 : Heaps (data structures)

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。