히프
보통 힙(최대힙) : 리프-루트 경로를 따르는 모든 키가 오름차순으로 되어있는 완전 이진 트리
어떤 키도 부모보다 크지 않음.
* 최소힙 : 부모키가 자식키보다 작
히프화 연산
히프 특성 만족하도록 시퀀스 원소들 재배열하는 것.
리프-루트 경로 따라 인접한 두 개 이상의 원소를 회전
우선순위 큐
원소의 우선순위에 삭제 연산이 수행되는 큐
어떤 것이 높은 우선순위를 가지는지 결정하기 위해 원소들 간의 비교가 가능하다는 것을 가정하고 있음.
일반적 큐 : 선입선출(FIFO), 우선순위 큐 : 최적입선출(BIFO)
어떤 것을 먼저 넣느냐가 중요한 게 아니라, 그냥 우선순위인 것이 먼저 나감.
따라서 힙을 이용하는 것이 편함!
즉, 연산이 어떻게 진행되냐면,
삽입 : 주어진 원소를 넣으면, 트리의 말단에 넣어짐. 여기서 히프화 연산을 통해 원소가 자리를 찾아감.
삭제 : 루트를 삭제하고, 말단을 다시 루트에 넣고 히프화 연산 수행.
