바이너리 힙의 배열 표현

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

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

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

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

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

• 루트 요소의 인덱스는 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!