[자료구조] 힙(Heap)이 뭘까?

 

 

힙이란?

 

힙(Heap)은 데이터에서 최대값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree) 입니다.

 

이진 트리(Binary Tree)는 트리 중에서도 각 노드가 최대 2개의 자식노드를 가질 때 이진트리(Binary Tree)라고 합니다. 

 

항상 최대/최소의 값들이 필요한 연산이 있다면 힙을 사용하면 되겠습니다.

 

Python3의 경우에는 heapq 라던가 힙 구조화 시켜주는 heapify 함수가 있지만 JavaScript는 그런 함수가 없습니다.. 따로 구현을 해서 사용을 해야한답니다

 

힙은 항상 큰 값이 상위레벨이 있으며 작은 값이 하위 레벨에 있도록 하는 자료구조입니다.

다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 합니다. 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 가야겠죠?

따라서 최대의 값들을 빠르게 구할 수 있게 되는 것입니다.

 

 

같이 예시를 보시죠

 

      8      Level 0
    6   3    Level 1
     2 1     Level 2  # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!

      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 1     Level 2  # 자식 노드보다 크니까 힙이 맞습니다!


      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 5     Level 2  # 자식 노드보다 크지 않아서 힙이 아닙니다..!

 

힙은 다음과 같이 최대값을 맨 위로 올릴수도 있고, 반대로 최솟값을 맨 위로 올릴 수도 있습니다.

 

최대값이 맨위에 있으면 최대힙(Max heap), 최소값이 맨위에 있으면 최소힙(Min heap)이라고 합니다.

 

 

• BST(이진탐색트리)와 다릅니다. 좌, 우 자식의 위치가 대소관계를 반영하지 않습니다. 
  • BST(이진탐색트리)는 왼쪽 자식은 부모보다 작아야하고, 오른쪽 자식은 부모보다 커야합니다.
• 계산 편의를 위해 인덱스(Index)는 1부터 사용한다. 보통 최상단 부모 인덱스는 null을 사용합니다.
  • parent: x, left: 2x, right: 2x+1

 

 

최대 힙(Max heap) - 샵입 알고리즘

 

 

최대 힙(Max heap)의 규칙

- 힙은 항상 큰 값이 상위레벨에 있고 작은 값이 하위레벨에 있어야합니다.

 

따라서, 원소를 추가하거나 삭제할때도 위의 규칙이 지켜져야 합니다!
원소를 추가할 때는 다음과 같이 하시면 됩니다.

1. 원소를 맨 마지막에 추가합니다.
2. 그리고 부모노드와 비교합니다. 만약 더 크다면 자리를 바꿉니다.
3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2. 과정을 반복합니다.

예시를 보겠습니다!

 

이 맥스 힙에서 9를 추가해보겠습니다!
      8      Level 0
    6   3    Level 1  
   4 2 1     Level 2 

1. 맨 마지막에 원소를 넣습니다.

      8      Level 0
    6   3    Level 1  
   4 2 1 9   Level 2 

2-1. 부모 노드와 비교합니다. 3보다 9가 더 크니까! 둘의 자리를 변경합니다.

      8      Level 0
    6   3    Level 1  
   4 2 1 9   Level 2 

      8      Level 0
    6   9    Level 1  
   4 2 1 3   Level 2 

2-2. 다시 부모 노드와 비교합니다. 8보다 9가 더 크니까! 둘의 자리를 변경합니다.

      8      Level 0
    6   9    Level 1  
   4 2 1 3   Level 2 

      9      Level 0
    6   8    Level 1  
   4 2 1 3   Level 2 

3. 가장 위에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삽입했습니다!

      9      Level 0
    6   8    Level 1  
   4 2 1 3   Level 2

 

 

다음으로 최대 힙(Max heap) 삽입의 시간복잡도를 알아보겠습니다.

 

최대 힙 삽입은 결국 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올리고 있습니다.

완전 이진트리의 최대 높이는 O(log(N))입니다. 그러면, 반복하는 최대 횟수도 O(log(N))일겁니다.

즉! 맥스 힙의 원소 추가는 O(log(N))만큼의 시간 복잡도를 가진다고 분석할 수 있습니다.

 

 

최대 힙(Max heap) - 추출 알고리즘

 

최대 힙(Max heap)에서 원소를 추출하는 방법은 최댓값, 루트 노드를 삭제하는 것입니다.

 

스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수는 없습니다.

 

최대 힙(Max heap)에 원소를 추가했던 것과 마찬가지로 원소를 삭제할때도 힙의 규칙이 지켜져야 합니다.

 

삽입 알고리집에서 알아보았던 것 처럼 진행순서를 알아보겠습니다.

 

1. 루트 노드와 맨 끝에 있는 원소를 교체합니다.

2. 맨 뒤에 있는 원소를 [원래 루트 노드] 삭제합니다.

3. 변경된 노드와 자식 노드들을 비교합니다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꿉니다.

4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때 까지 3. 과정을 반복합니다.

5. 2에서 제거한 원래 루트 노드를 반환합니다.

 

예시를 통해 좀 더 쉽게 이해해보도록 하겠습니다.

 

이 맥스 힙에서 원소를 제거해보겠습니다! (항상 맨 위의 루트 노드가 제거 됩니다.)
      8      Level 0
    6   7    Level 1  
   2 5 4 3   Level 2 

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

      8      Level 0
    6   7    Level 1  
   2 5 4 3   Level 2 

      3      Level 0
    7   6    Level 1  
   2 5 4 8   Level 2 

2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제합니다. 
이 값이 기존 맥스힙에 있던 가장 큰 값입니다. 따라서 이 값을 마지막에는 반환해줘야 합니다!

      3      Level 0
    6   7    Level 1  
   2 5 4 X   Level 2 

3-1. 변경된 노드를 더 큰 자식 노드와 비교해야 합니다. 
우선 부모와 왼쪽 자식을 비교합니다. 그리고 부모와 오른쪽 자식을 비교합니다.
그리고 부모 보다 큰 자식 중, 더 큰 자식과 변경해야 합니다.
왼쪽 자식인 6과 오른쪽 자식인 7 중에서 7이 더 크고, 부모인 3보다 크니까 둘의 자리를 변경합니다.

      3      Level 0
    6   7    Level 1  
   2 5 4     Level 2 

      7      Level 0
    6   3    Level 1  
   2 5 4     Level 2 

3-2. 다시 자식 노드와 비교합니다. 
우선 부모와 왼쪽 자식을 비교합니다.
왼쪽 자식인 4는 부모인 3보다 더 크니까 둘의 자리를 변경합니다.

      7      Level 0
    6   3    Level 1  
   2 5 4     Level 2 

      7      Level 0
    6   4    Level 1  
   2 5 3     Level 2 


4. 가장 아래 레벨에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삭제했습니다!

      7      Level 0
    6   4    Level 1  
   2 5 3     Level 2 

5. 그리고, 아까 제거한 원래 루트 노드, 8을 반환하면 됩니다!

 

마지막으로, 최대 힙(Max heap) 추출 알고리즘의 시간복잡도를 알아보겠습니다.

추출 또한 삽입과 마찬가지로 결국 원소를 맨 위에 올려서 바닥까지 비교하면서 내리고 있습니다.

맥스 힙의 원소 삭제도 O(log(N)) 만큼의 시간 복잡도를 가진다고 분석할 수 있습니다.

 

 

정리

 

힙(heap)은 탐색트리의 일종이며, 이진 탐색트리 구조입니다. 이진탐색트리는 최대 2개의 자식노드를 가지고있는 데이터 구조입니다.

최대힙(Max heap) 삽입과 추출은 사소한 규칙의 변화가 있을 뿐, 같은 알고리즘을 가지고 있습니다.

 

삽입은 데이터구조의 끝에 삽입할 요소를 추가합니다. 이후 추가한 요소의 위치를 len으로 파악한뒤 //2 연산을 통해 부모노드를 찾아내고 누가 더 큰지 비교합니다. 자식요소가 부모요소보다 크다면 자리를 바꾸는 로직을 반복하고 데이터 구조 최 상단으로 이동하거나 더이상 자식요소가 부모요소보다 크지않다면 삽입 알고리즘 진행은 종료됩니다.

 

추출은 항상 최대힙에서는 가장 큰 값(최상단)의 노드를 추출합니다. 먼저, 최상단에 있는 루트노드를 최하단에 있는 노드와 교체합니다. 이후 최하단으로 이동한 최대값 루트 노드를 제거합니다. (추출 알고리즘에서 반환할 값입니다.) 이후 삽입에서 진행했던 알고리즘처럼 부모와 자식 노드간의 크기를 비교하며 ( //2 연산 ) 데이터구조를 정리하면 됩니다. 여기서 주의해야할 점은 왼쪽과 오른쪽 자식 노드 중 더 큰 자식 노드와 위치를 바꿔야합니다. 마찬가지로 더이상 자식 노드가 부모 노드보다 크지않다면 데이터구조 정리가 마무리되게 되고, 앞서 제거했던 최대값 루트노드를 반환하면 추출 알고리즘 진행도 종료됩니다.