비프

비프(bi-parental heap)는 보통 노드가 2개의 부모(레벨의 첫 번째 또는 마지막이 아닌 경우)와 2개의 자식(마지막 레벨이 아닌 경우)을 갖는 데이터 구조입니다.힙과 달리 비프는 하위 선형 검색을 허용합니다.비프는 Ian Munro와 Hendra Suwanda에 의해 소개되었다.관련된 데이터 구조는 영 테이블로입니다.

비프

성능

구조물의 높이는 약 ${$입니다.또한 마지막 레벨이 꽉 찼다고 가정하면 해당 레벨의 요소 수도 ${$$n$$\}\}$이 됩니다.실제로 이러한 속성 때문에 O$)$에서 $실행$되는 모든 기본 조작(삽입, 제거, 찾기)은 {$n}$에서 실행됩니다.평균$$ }회입니다$.$힙에서 찾기 작업은 최악의 경우 O${\displaystyle }$(${\displaystyle n}$) \ $displaystyle$ O$(n)$가 될 수 있습니다.새로운 요소의 제거 및 삽입에는 비프 불변성을 복원하기 위해 요소의 위 또는 아래(히프 내와 거의 동일) 전파가 포함됩니다.또한 beap은 최소 요소에 대한 상시 $액세스$와 최대 요소에 $대한$O (${\displaystyle }$n $)$ \ $displaystyle$O ( { \$sqrt$ { n$$} )시간을$$ 제공합니다.

실제로 각 노드의 부모 포인터가 유지되면 O${\displaystyle }$(${\displaystyle n\sqrt{}}$ $)(\style$ O ({\$sqrt {n}})$ find$$ $조작$을 구현할 수 있습니다.상위 노드의 맨 아래 요소(히프 내의 맨 왼쪽 자 요소와 유사)에서 시작하여 위 또는 오른쪽으로 이동하여 관심 요소를 찾습니다.

레퍼런스

• Munro, J. Ian; Suwanda, Hendra (1980). "Implicit data structures for fast search and update". Journal of Computer and System Sciences. 21 (2): 236–250. doi:10.1016/0022-0000(80)90037-9.
• Williams, J. W. J. (Jun 1964). "Algorithm 232 - Heapsort". Communications of the ACM. 7 (6): 347–348. doi:10.1145/512274.512284.