> 백엔드 개발 > C++ > 바이너리 힙의 배열 표현

바이너리 힙의 배열 표현

PHPz
풀어 주다: 2023-09-04 22:45:05
앞으로
750명이 탐색했습니다.

힙 정렬 속성을 따르는 완전한 이진 트리를 이진 힙이라고 합니다.

바이너리 힙이 정렬되는 방식에 따라 두 가지 유형으로 나눌 수 있습니다.

최소 힙은 노드 값이 상위 노드 값보다 크거나 같은 힙입니다. 최소 힙의 루트 노드는 가장 작습니다.

최대 힙은 노드 값이 상위 노드 값보다 작거나 같은 힙입니다. 최대 힙의 루트 노드가 가장 큽니다.

바이너리 힙의 값은 일반적으로 배열으로 표시됩니다. 바이너리 힙의 배열 표현은 다음과 같습니다.

  • 루트 요소의 인덱스는 0입니다.

  • i가 배열에 있는 노드의 인덱스인 경우 해당 노드와 관련된 다른 노드의 인덱스는 다음과 같습니다.

    • 왼쪽 자식: (2*i)+1

    • 오른쪽 자식 : (2*i )+2

    • 상위 노드: (i-1)/2

위의 배열 표현 규칙을 사용하여 힙을 배열로 표현할 수 있습니다.

바이너리 힙의 배열 표현

1 4 7 8 9 11 12

이제 정렬 기반 힙의 유형에 대해 논의할 수 있습니다.

  • 최소 힙 - 루트 노드는 최소값을 갖습니다. 노드의 값이 상위 노드의 값보다 큽니다.

예:

바이너리 힙의 배열 표현

배열 표현:

1 4 7 6 9 10 8
  • 최대 힙 - 루트 노드가 최대값을 가집니다. 노드의 값이 상위 노드의 값보다 작습니다.

예:

바이너리 힙의 배열 표현

배열 표현:

11 8 9 6 4 5 1

위 내용은 바이너리 힙의 배열 표현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:tutorialspoint.com
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
최신 이슈
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿