정렬: heap(priority queue)

좌우 트리가 균형적일 경우에는 배열로 표현하는 것이 유리합니다.

장점 - 리스트로 구현할 때 소비되는 연결 포인터에 대한 메모리 공간을 절약할 수 있고

포인터 연산에 필요한 메모리 접근을 수식 연산으로 대체합니다.

메모리 접근 비용보다 수식 연산이 빠릅니다.

단점 - 배열 크기를 사전에 결정하여 할당해야 하기 때문에 구현 시 배열 크기가 가늠이 되지 않을 경우에는 사용이 어렵고 사전에 결정이 가능하다고 하더라도 시작부터 전체 메모리를 할당하고 시작해야 하기 때문에 메모리를 효율적으로 사용하기 어렵습니다.

왼쪽 자식 인덱스	(2 x 부모 인덱스) + 1
오른쪽 자식 인덱스	왼쪽 자식 인덱스 + 1
부모 인덱스	(자식 인덱스 - 1) / 2

트리를 배열로 표현

heap

힙은 완전 이진 트리를 이용하여 힙에 값을 넣을 때나 뽑을 때 항상 최대 또는 최소 값을 정렬하여 저장하도록 구성됩니다.

완전 이진 트리의 부모는 자식보다 클 때 루트가 최대값을 가지는 최대 힙을

부모가 자식보다 작을 때 최소값을 가지는 최소 힙을 구현할 수 있습니다.

1) 삽입 방법 - 배열의 끝에 추가한 후 부모와 자식의 관계를 이용하여 위로 재 정렬 합니다.

2) 추출 방법 - 루트를 추출하여 사용한 후 배열의 끝 원소를 루트 자리로 옮긴 다음 아래로 정렬 합니다.

priority queue

각 원소가 우선 순위를 가지고 있을 때 큐에서 최소 또는 최대 우선 순위의 원소를 추출하는 기능을 가지고 있는 자료 구조를 우선 순위 큐라고 합니다.

우선 순위 큐는 힙을 이용하여 구현하는 것이 일반적이며 우선 순위 기능을 구현하기 용이한 다른 자료 구조로 구현 할 수도 있습니다.