바이너리 힙의 배열 표현

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

바이너리 힙의 순서에 따라 두 가지 유형이 될 수 있습니다.

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

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

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

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

• i가 배열에 있는 노드의 인덱스인 경우. 그런 다음 해당 노드와 관련된 다른 노드는 -

  와 같이 배열의 인덱스입니다.

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

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

  • 부모자식 :(i-1)/2

위의 배열 표현 규칙을 사용하여 배열의 힙을 나타낼 수 있습니다 -

이제 순서를 기반으로 하는 힙 유형을 여기에서 논의할 수 있습니다.

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

예 -

배열 표현 -

• 최대 힙 − 루트 노드에는 최대 노드가 있습니다. 노드의 값이 상위 노드의 값보다 작습니다.

예 -

배열 표현 -