Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

힙 페어링

<시간/>

페어링 힙은 비교적 구현이 쉽고 실용적인 상각 성능이 뛰어난 힙 데이터 구조 유형으로 정의됩니다.

페어링 힙은 힙 순서의 다중 트리 구조이며 단순화된 피보나치 힙으로 표시할 수 있습니다.

그들은 Prim의 MST 알고리즘과 같은 알고리즘을 구현하기 위한 "강력한 선택"으로 간주되며 다음 작업을 지원합니다(최소 힙 가정) -

  • 최소 찾기 − 이 함수는 힙의 최상위 요소를 반환하는 역할을 합니다.
  • 융합 −이 함수는 두 루트 요소를 비교하는 역할을 합니다. 작은 요소는 결과의 루트로 남아 있고, 큰 요소와 하위 트리는 이 루트의 자식으로 추가됩니다.
  • 삽입 − 이 함수는 삽입된 요소에 대한 새 힙을 만들고 원래 힙에 병합하는 역할을 합니다.
  • 감소 키(선택 사항) − 이 함수는 감소할 키에 뿌리를 둔 하위 트리를 제거하고 키를 더 작은 키로 교체한 다음 결과를 다시 힙에 병합하는 역할을 합니다.
  • 최소 삭제 - 이 함수는 루트를 제거하고 하나의 트리가 남을 때까지 하위 트리를 반복적으로 혼합하는 역할을 합니다. 다양한 병합 전략이 사용됩니다.
  • 각 노드에는 왼쪽 자식을 가리키는 포인터가 있고 왼쪽 자식은 자식의 다음 형제를 가리킵니다.
  • 힙 페어링의 예는 다음과 같습니다. -

힙 페어링

힙 페어링의 시간 복잡도 분석은 주로 스플레이 트리 분석에서 영감을 받았습니다. delete-min당 상각 시간은 O(log n)으로 간주되며 find-min, meld 및 insert 작업은 O(1) 상각 시간에 실행됩니다.