[자료구조] 우선순위 큐, 히프

priority queue(우선순위 큐)의 가장 효율적인 구현 방법은 heap

히프 : 여러 개의 값들 중, 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조.

완전 이진 트리의 일종.

삽입, 삭제 연산의 복잡도 : O(log(n))  //트리 구조는 높이! logn

max heap(최대 히프)

 : 부모 노드의 키값 >= 자식 노드의 키값

min heap(최소 히프)

 : 부모 노드의 키값 <= 자식 노드의 키값

구현 : 히프는 완전 이진 트리로 인덱스가 정해져있기 때문에 일차원 배열에 저장할 수 있다.

왼쪽 자식 인덱스 : (부모 인덱스)*2;

오른쪽 자식 인덱스 : (부모 인덱스)*2+1;

부모 인덱스 = (int)((자식 인덱스)/2);

1. 삽입 연산

히프의 가장 마지막에 새로운 원소를 삽입하고, 부모노드와 비교해가면서 한 단계씩 올라간다.

2. 삭제 연산

ex.최대 히프 - 최댓값 원소를 삭제하는 것.

1. 루프 노드를 삭제한다.

2. 가장 마지막 인덱스인 노드를 루프 노드 자리에 올리고, 자식노드의 키값과 비교해가면서 한 단계씩 내려간다.

3. 히프 정렬 (heap sort) : O(n*log_2(n))

유리할 때 : 가장 큰 값, 또는 가장 작은 값 중 몇 개만 필요할 때.

방법 : 

오름차순 정렬 -> min heap 사용 -> 삭제연산을 반복하면서 return값들 순서대로

내림차순 정렬 -> max heap 사용 -> 삭제 연산을 반복하면서 return값들 순서대로

4. 허프만 코드