TArray - 힙

힙

TArray에는 이진 힙 데이터 구조체를 지원하는 함수가 있다.

힙은 부모 노드가 그 자손 노드 전부의 이전 또는 동등한 위치에 있는 이진트리 유형이다.
배열로 구현되면, 트리의 루트노드는 엘리먼트 0이며, N 인덱스 노드의 좌우 자손 인덱스는 각각 2N+1 과 2N + 2이다.
Heapify 함수를 사용하여 기존 배열을 힙으로 변환시킬 수 있다.
술부가 있을 수도 없을 수도 있는데, 술부가 없는 버전은 순서 결정에 엘리먼트 유형의 연산자 < 를 사용

 

 

TArray<int32> HeapArr;
for (int32 Val = 10; Val != 0; --Val)
     HeapArr.Add(val);
// HeapArr == [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
HeapArr.Heapify();
// HeapArr == [1, 2, 4, 3, 6, 5, 8, 10, 7, 9]

이진 힙을 사용하는 이유는 최소값과 최댓값을 찾기가 쉬운 자료구조이기 때문이다.힙화된 배열의 엘리먼트 순서대로 트리의 노드는 왼쪽에서 오른쪽, 위에서 아래로 읽을 수 있다.참고로 배열은 힙으로 변환시킨 이후 반드시 Sorting할 필요가 없다.Sorting된 배열 역시 유효한 힙이 될 수는 있지만, 힙 구조체 정의는 공간이 충분해서 똑같은 엘리먼트 세트에 대해 다수의 유효한 힙이 가능

HeapPush

함수로 힙에 새로운 엘리먼트를 추가할 수 있으며, 힙 유지를 위해 다른 노드 순서를 변경

HeapArr.HeapPush(4);
// HeapArr == [ 1, 2, 4, 3, 4, 5, 8, 10, 7, 9, 6 ]

HeapPop

HeapPop과 HeapPopDiscard 함수는 힙의 맨 위 노드를 제거하는 데 사용.그 둘의 차이점은, 전자는 엘리먼트 유형으로의 레퍼런스를 받아 맨 위 엘리먼트 사본을 반환하는 반면, 후자는 어떤 식으로든 반환 없이 맨 위 노드를 그냥 제거한다.두 함수 모두 배열에 가하는 변화는 같으며, 힙의 순서 역시 다른 엘리먼트를 적절히 변경하여 유지된다.

int32 TopNode;
HeapArr.HeapPop(TopNode);
// TopNode == 1
// HeapArr == [2, 3, 4, 6, 4, 5, 8, 10, 7, 9]

HeapArr.HeapPopDiscard();
// 그냥 TopNode 삭제
// HeapArr == [2, 3, 4, 6, 4, 5, 8, 10, 7, 9]

HeapRemoveAt

배열에서 주어진 인덱스의 엘리먼트를 제거한 뒤, 엘리먼트 순서를 변경하여 힙을 유지시킵니다.

HeapArr.HeapRemoveAt(1);
// HeapArr == [ 2, 4, 4, 6, 9, 5, 8, 10, 7]

HeapPush, HeapPop, HeapPopDiscard, HeapRemoveAt, 은 구조체가 이미 유효한 힙일 경우, 즉 Heapify 또한, Heapify 를 포함한 이 함수 각각은, 힙 내 노드 엘리먼트의 순서 결정을 위한 2항 술부를 옵션으로 받을 수 있다.기본적으로 힘 연산은 엘리먼트 유현의 operator< 를 사용하여 순서를 결정합니다.커스텀 술부를 사용하는 경우, 모든 힙 연산에 같은 술부를 사용하는 것이 중요.

HeapTop

• 힙의 맨 위 노드를 조사할 수 있으며, 배열은 변경되지 않음

int32 Top = HeapArr.HeapTop();
// Top == 2