병합 가능한 힙

Mergeable heap

컴퓨터 과학에서 병합 가능한 힙(meldable 힙이라고도 함)은 병합 작업을 지원하는 힙인 추상 데이터 유형입니다.

정의.

병합 가능한 힙은 일반적인 힙 [1]작업을 지원합니다.

  • Make-Heap()빈 힙을 만듭니다.
  • Insert(H,x), 요소를 삽입합니다.x산더미처럼 쌓여서H.
  • Min(H), 최소 요소를 반환합니다.Nil이러한 요소가 존재하지 않는 경우.
  • Extract-Min(H), 최소 요소를 추출하여 반환합니다.또는Nil이러한 요소가 존재하지 않는 경우.

그리고 그것을 [1]구별하는 또 하나의 특징:

  • Merge(H1,H2), 의 요소를 조합합니다.H1그리고.H2한 무더기로 만들다

간단한 구현

단순한 힙을 지정하면 머지 가능한 힙을 구현하는 것은 간단합니다.

Merge(H1,H2):

  1. x ← Extract-Min(H2)
  2. while x ≠ Nil
    1. Insert(H1, x)
    2. x ← Extract-Min(H2)

단, 이것은 각각으로 인해 낭비가 될 수 있습니다.Extract-Min(H)그리고.Insert(H,x)는 일반적으로 힙 속성을 유지해야 합니다.

보다 효율적인 구현

병합 가능한 힙 데이터 구조의 예는 다음과 같습니다.

성능 비교가 포함된 보다 완전한 목록은 힙(데이터 구조) » 변종 이론상의 한계 비교에서 확인할 수 있습니다.

대부분의 병합 가능한 힙 구조에서 병합은 다른 힙 구조의 기반이 되는 기본 작업입니다.삽입은 새로운 단일 요소 힙을 기존 힙과 병합하여 구현됩니다.삭제는 삭제된 노드의 자식을 Marge함으로써 구현됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 505–506. ISBN 0-262-03384-4.