[알고리즘] 힙과 우선순위 큐, 둘의 차이점

힙

최대 힙은 완전 이진트리이고, 부모가 항상 자식보다 큰 자료구조이다.

완전 이진트리란, 마지막 레벨을 제외하고 모든 레벨의 노드가 다 채워져 있고 마지막 레벨은 왼쪽부터 채워지는 트리이다.

 

최소 힙은 반대로 부모가 항상 자식보다 작다. 힙은 완전 이진트리의 특성상 부모와 자식의 index가 명확해서 배열을 사용한다. A[i]의 부모는 A [i/2]이고 왼쪽 자식은 A [2*i] 오른쪽 자식은 A [2*i + 1]이다. 힙은 힙 특성 유지하기(heapify), 힙 만들기(buildHeap), 삽입(insert), 삭제(delete)만 알면 된다.

---

 

힙 구현

힙 특성 유지하기(heapify)

배열 A에 대해 i번째 원소를 최대힙의 루트가 되게 한다. 아래는 퍼수도 코드이다.

heapify(A, i){ 
    l = A[i].left 
    r = A[i].right 
    
    if(l < A.size && A[l] > A[i]) 
    	max = l 
    else max = i 
    
    if(r < A.size && A[r] > A[max]) 
    	max = r 
        
	if(largest != i){ 
    swap(A[i], A[max]) 
    heapify(A, max) 
    } 
}

heapify는 상수시간이 걸리고 최악의 경우에도 힙의 높이인 log n 만큼 호출하므로 시간복잡도는 log n이다.

​

힙 만들기(buildHeap)

heapify를 리프를 제외한 노드들에 대해 수행하면 된다.

buildHeap{ 
  for(i = A.size/2; i > 0; i--) heapify(A, i)
}

heapify를 n/2번 호출하므로 시간복잡도는 nlog n이다. insert를 n번 호출해서 힙을 만드는 경우도 있다. 이 방법을 더 자주 쓰는 것 같다. 시간 복잡도는 똑같이 nlog n이다.

​

삽입(insert)

삽입할 노드를 가장 마지막에 삽입하고, 부모와 교환하면서 힙 특성을 맞춰주면 된다.

insert(A, x){
  //n은 현재 힙 사이즈+1 (0번째는 사용 x)
  A[++n] = x; 
  for(i = n; i > 1; i /= 2){ 
  if(A[i] > A[i/2]) swap(A[i], A[i/2]) 
  else break 
  } 
}

시간 복잡도는 nlog n이다.

​

삭제(delete)

루트를 삭제하고, 마지막 원소를 루트 위치로 이동시킨 뒤 다시 특성을 유지시킨다.

delete(A){
  A[1] = A[n] 
  A[n--] = 0 
  for(i = 1; i < n;){
    if(A[i] > A[i*2] && A[i] > A[i*2+1]) break; 
    else if(A[i] < A[i*2]){ 
      swap(A[i], A[i*2]) i *= 2 
    } else{ 
      swap(A[i], A[i*2]) i = i*2 + 1 } 
  } 
}

시간 복잡도는 n log n이다. 힙 관련 문제는 우선순위 큐 관련 문제를 풀면서 같이 공부하는 게 나을 것 같다.

---

우선순위 큐

우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. 우선순위 큐는 배열, 연결리스트, 힙으로 구현할 수 있고 보통 힙으로 구현한다. 배열이나 연결리스트로 구현할 경우 삽입의 시간복잡도가 O(n)이 나오고 힙으로 구현하면 O(log n)이 나온다. 기본적으로 우선순위 큐는 원소를 추가하는 insert, 가장 우선순위가 높은 원소를 제거하고 반환하는 pull연산을 지원해야 한다.

---

힙과 우선순위 큐의 차이점

힙과 우선순위 큐를 처음 배우면 둘이 똑같은 거 아닌가??라는 생각이 든다. 내가 생각하는 핵심적이 차이는 힙은 트리 기반의 자료구조이고 우선순위 큐는 우선순위에 따라 원소들이 push, pull되는 큐라는 점이다. 우선순위 큐라는 추상 자료형을 heap이라는 자료구조로 구현하는 것이 보통이다. 기능은 거의 똑같지만 우선순위 큐는 큐이고 힙은 이진트리라는 점이 큰 차이인 것 같다.