항해99 TIL 2주차 - 11

오늘은 힙에 대해 배웠는데 최근에 배웠던 DFS,BFS,이진트리에 비해 상대적으로 쉬웠던것같다. 힙도 이진트리 중 하나이지만 확실히 라이브러리가 있어서 그런지 쉬웠다

힙

힙이란 데이터 중 최대값과 최소값을 구할때 사용하면 편한 자료구조 중 하나이다.
힙은 부모노드가 자식노드보다 크다는 특징이 있지만 항상 그런것은 아니다. 힙이 최대 힙인지 최소 힙인지에 따라 달라진다.
최대 힙이라면 부모노드가 자식노드보다 크지만 최소 힙일 경우 부모노드가 자식노드보다 작게된다.

최대 힙

최대 힙 삽입 알고리즘

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. 삽입한 노드의 부모노드와 값을 비교한다, 부모노드보다 값이 크다면 부모노드와 자식노드의 위치를 바꾼다.

      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      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

최대 힙 추출 알고리즘

가장 큰 원소 값 추출

      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. 가장 위의 있는 노드의 값과 자식노드의 값을 비교하면서 자식노드보다 값이 작지 않을때까지 비교하며 내려온다.

      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. 계속해서 자식노드와 비교하며 내려오는 모습
노드 3의 자식노드는 왼쪽노드밖에 없으므로 왼쪽노드의 값인 4와 비교
하고 3은 4보다 값이 작으므로 자리 변경

      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을 반환