1일1개 (45) - 자료구조의 힙합

1일 1개념정리 24.08.09.금 ~ 

 

큰 결정에 큰 동기가 따르지 않을 때도 있다. 하지만 큰 결심이 따라야 이뤄낼 수 있다.

무조건 무조건 1일 1개의 개념 정리하기 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!

---

#45. Heap

Heap은 Java 메모리 구조 등에서도 자주 언급되는데, 그거랑은 다르다. 이건 자료구조의 이름이고, java에선 메모리 영역의 이름으로 불린다. 아무튼 이번에 본 시험에서 최대힙에 대해서 다루길래 한번 정리해본다.

 

힙이란 ?

힙은 완전 이진 트리의 한 종류로, 부모 노드와 자식 노드 간 특정한 규칙이 있는 트리형 자료구조이다. 일반적으로 우선순위 큐를 구현할 때 많이 사용한다. 힙의 가장 중요한 특징은 부모 노드가 자식 노드보다 항상 크거나(최대힙) 작아야(최소힙) 한다는 것이다. 여기서 말하는 "완전 이진 트리"란?? 완전 이진 트리는 모든 레벨이 다 채워져 있으며, 삽입시 왼쪽부터 차례대로 노드가 채워진 트리이다.

 

앞서 말했듯, 힙은 2가지로 나뉜다.

 

1. 최대 힙 (Max Heap) : 부모 노드가 자식 노드들보다 항상 크거나 같음.

즉, 트리에서 가장 큰 값이 항상 루트 노드에 위치한다는 뜻이다. (매우중요) 그럼 반대로 최소힙은? 그렇다. 최소값이 루트에 있을 것이다.

 

이러한 특징 때문에 삽입이나 삭제가 이루어질 때 트리 구조를 재정비해야한다. 50이 최댓값인 최대힙에 100이 들어오면 100이 root로 가야하기 때문이다.

• 삽입 : 값을 삽입할 땐 트리의 가장 마지막 자리에 일단 넣고, 노드 값 비교하면서 위치 재조정한다.
• 삭제 : 삭제는 루트노드만 삭제 가능하다. 루트 노드가 삭제되면 트리에서 "가장 마지막에 있는 노드"가 루트로 이동한 뒤, 자식 노드들과 비교하며 더 큰 자식들과 교환하며 내려간다.

1-1. 최대힙 예시 (Max heap)

       50
      /  \
    30    20
   /  \   /
  15   10 5

 

2. 최소 힙 (Min  Heap) : 부모 노드가 자식 노드들보다 항상 작거나 같음.

즉, 최대힙과 반대로 root에 최소값이 있다는 것이다. 삽입, 삭제는 최대힙과 매커니즘이 동일하다. 다만 작은 값이 위로 올라간다는 것이 다르다.

• 삽입 : 삽입시 값은 트리의 가장 마지막 자리에 삽입되고, 부모 노드와 값 비교하며 작은 것이 올라간다.
• 삭제 : 삭제는 루트노드만 삭제 가능하다. 루트 노드가 삭제되면 트리에서 가장 마지막에 있는 노드가 루트로 이동한 뒤, 자식 노드들과 비교하며 작은 값이 올라간다. 왜 가장 마지막 노드가 올라오냐면, 완전 이진트리는 삽입시 왼쪽부터 차례대로 채워나가야하고 모든 레벨에 빠진 element가 있으면 안되니까 마지막 노드를 올리면 이 조건을 충족하기 때문이다.

2-1. 최소힙 예시 (Min heap)

       5
      /  \
    10    20
   /  \   /
  15   30 50

---

 

3. 삽입, 삭제 예시

삽입, 삭제 예시를 살펴보자 !!! 최소힙은 최대힙처럼 하되 작은 것이 올라간다는 맥락이므로 최대힙만 같이 알아보자.

 

3-1. 삽입 예시 - 최대힙

 

초기 상태는 다음과 같다.

        80
       /  \
      70   60
     /  \   / \
    50  65 55 45
   / \
  30  40

 

여기에 85를 추가해보자. 가장 마지막 자리에 추가한다.

       80
      /  \
     70   60
    / \   / \
   50  65 55 45
  / \  /
 30 40 85

 

여기서부터 이제 계속 부모노드와 위치를 비교해가며 자리를 바꿔간다. 65가 부모니깐 65랑 비교하고 교환한다.

       80
      /  \
     70   60
    / \   / \
   50  85 55 45
  / \  /
 30 40 65

 

다시 70과 비교한다. 교환

       80
      /  \
     85   60
    / \   / \
   50  70 55 45
  / \  /
 30 40 65

 

다시 80과 비교한다. 교환

       85
      /  \
     80   60
    / \   / \
   50  70 55 45
  / \  /
 30 40 65

 

완성

 

 

3-2. 삭제 예시 - 최대힙

아까 있었던 예시에서 삭제를 해보자. root에서만 삭제가 가능하다 했으니 최대값인 85를 삭제해본다.

        
       /  \
      70   60
     /  \   / \
    50  65 55 45
   / \
  30  40

 

이때, 가장 마지막에 있는 노드가 root로 올라온다. 앞서 말했듯, 왜 가장 마지막 노드가 올라오냐면, 완전 이진트리는 삽입시 왼쪽부터 차례대로 채워나가야하고 모든 레벨에 빠진 element가 있으면 안되니까 마지막 노드를 올리면 이 조건을 충족하기 때문이다.

 

그러므로 40을 올린다.

        40
       /  \
      70   60
     /  \   / \
    50  65 55 45
   / \
  30

 

여기서부터 교환을 시작하면 된다. 40은 70, 60 둘 다보다 작은데 뭐랑 교환할까? 이땐 큰 값이랑 교환한다. 왜냐면 어차피 60이랑 교환해도 다시 70이랑 교환해야하기 때문이다. 따라서 70과 교환

        70
       /  \
      40   60
     /  \   / \
    50  65 55 45
   / \
  30

 

40을 50과 65와 비교해서 65와 교환

        70
       /  \
      65   60
     /  \   / \
    50  40 55 45
   / \
  30

 

완성.