힙(Heap)
힙은 트리 구조로 '우선순위 큐(priority queue)'를 구현할 때 사용된다.
힙 자료구조는 최대 힙(Max Heep)과 최소 힙(Min Heep)으로 나뉘며 이러한 힙은 최대값 또는 최소값을 짧은 시간내에 찾을 수 있다.
우선순위 큐
- 데이터를 추가할 때는 자유롭게 추가할 수 있다.
- 데이터를 추출할 때는 우선순위가 높은 값부터 추출한다.
힙의 구조
- 최소 힙(Min Heap): 부모 노드의 숫자는 반드시 자식 노드의 숫자보다 작아야 한다.
- 최대 힙(Max Heap): 부모 노드의 숫자는 반드시 자식 노드의 숫자보다 커야 한다.
최소 힙에서의 삽입 (Insert Operation)
최소 힙에 숫자를 추가하는 경우
이미지 출처
1. 추가되는 수는 먼저 최고 깊이의 가장 오른쪽에 추가된다.
e.g.) 1은 4의 오른쪽 자식 노드에 추가된다.
2. 추가된 뒤 부모의 숫자가 큰 경우 부모와 자식을 교환한다.
e.g.) 부모 6 > 자식 1 교환
부모 4 > 자식 1 교환
부모 2 > 자식 1 교환
3. 이런 처리를 힙의 규칙에 만족힐 때까지 반복한다.최소 힙에서의 최소값 삭제 (Extract-Min Operation)
힙에서 숫자를 꺼낼 때는 가장 위에 있는 숫자(Root Node)가 추출된다.
루트 노드가 없어졌으므로 힙의 구조를 다시 정리해야 한다.
이미지 출처
1. 최고 깊이의 가장 오른쪽 노드를 루트로 이동시킨다.
e.g.) 6이 루트 노드로 이동한다.
2. 부모의 숫자보다 자식의 숫자가 작은 경우 자식의 좌우 노드 중 더 작은 쪽과 교환한다.
e.g.) 좌 2 < 우 3 이므로 왼쪽 자식과 교환한다.
부모 6 > 자식 2 교환
3. 이런 처리를 힙의 규칙에 만족할 때까지 반복한다.
e.g.) 좌 4 < 우 9 이므로 왼쪽 자식과 교환한다.
부모 6 > 자식 4 교환 최소 힙을 사용하면 최솟값을 빠르게 추출할 수 있다.
단, 가운데 있는 데이터를 추출할 수는 없다.
힙은 우선순위 큐나 다익스트라 기법 등에서 사용되고 있다.
