Heap(힙)

Heap 이란?

일반적인 큐(Queue)는 FIFO의 특징을 갖지만 우선순위 큐는 우선순위가 높은 요소를 먼저 내보내는 특징이 있다. 이러한 우선순위 큐는 정해진 자료구조가 아닌 개념의 한 부분 이며, 우선순위 큐를 구현하기 위한 가장 적합한 방법이 힙 자료구조이다.

특징

• 루트 노드에 가장 큰 값이 놓여지는 최대 힙(Max heap)과 루트 노드에 가장 작은 값이 놓여지는 최소 힙(Min heap)이 있다.
• 이진 트리형태를 가지며, 요소가 삽입 삭제될 때 정렬이 되는 특징이 있다.

요소 추가(Max heap일 경우)

1. 요소가 추가될 때는 트리의 가장 마지막 노드에 위치한다.
2. 노드를 추가한 뒤 부모 노드와 비교하여 순서를 변경한다.
3. 이 과정을 계속 반복하면 가장 우선순위가 높은 노드가 루트에 위치한다.

요소 제거(Max heap일 경우)

1. 요소 제거는 루트 노드만 가능하다.
2. 루트 정점이 제거된 후 가장 마지막 노드가 루트에 위치한다.
3. 루트 노드의 두 자식 노드 중 우선순위가 더 높은 정점과 바꾼다.
   • 비교할 때 오른쪽부터 비교해야 우선순위가 잘 적용된다.
     ex) 부모노드가 40, 자식 노드가 50 50 일경우 왼쪽부터 비교하면 50 40 50으로 변경되지만 오른쪽부터 비교할 경우 50 50 40이 된다.)
4. 두 자식 노드의 우선순위가 더 낮을 때 까지 반복한다.

시간복잡도

완전이진트리의 높이는 logN이기에 힙의 요소 추가, 삭제 알고리즘의 시간복잡도는 O(logN)이다.