[자료구조] 9강 - 힙

✅ 1. 우선순위 큐

(1) 큐

• FIFO(First In First Out) - 먼저 들어온 데이터가 먼저 삭제되는 자료 구조 ( 먼저 처리되는 데이터 )

(2) 우선순위 큐

• 위의 큐 구조에서 만약 중간의 데이터를 먼저 빼고 싶은 경우가 존재 할 때 사용되는 큐가 우선순위 큐임.

• 즉, 우선순위가 높은 데이터가 먼저 처리가 되는 Queue 자료구조로 볼 수 있음.

(3) 우선순위 큐 - 배열 구현

• 위의 큐의 이미지는 배열 방식으로 구현 된 큐의 모습이다.
• 먼저 데이터가 삽입이 되면, rear 포인터가 오른쪽으로 움직이면서 해당 위치에 데이터가 삽입이 된다.
• 데이터를 꺼내는 작업(삭제 작업)을 하면 front 포인터가 한 칸씩 이동하면서 데이터를 꺼내면서 삭제하게 된다.

• 배열에 우선순위 큐를 접목하게 되면, 위와 같이 특정 조건에 해당하는 숫자를 front 앞 부분으로 옮기게 된다.
• 그러면 front 는 특정 조건에 해당하는 2(예시)를 front 앞 부분으로 옮기게 된다.
• 또한, 옮겨진 부분에는 기존의 큐에 순서에 맞게 정렬을 하게 된다. ( 보통 큰값/작은값을 우선순위 기준으로 씀 )
• 이렇게 배열로 구현한 우선순위 큐는 위와같이 오버헤드가 큰 작업을 수행 할 수 밖에 없게 된다.
• 오버헤드: 어떤 작업을 수행하기 위해 추가로 드는 비용을 의미함.

(4) 우선순위 큐 - 핵심

• 우선순위 큐는 배열로 구현하면 오버헤드가 많이 발생함.
• 그래서 우선순위 큐는 힙으로 구현하면 오버헤드를 줄일 수 있음.

---

✅ 2. 힙 추상 자료형

(1) 힙 - 정의

• 힙은 우선순위가 가장 높은 데이터만 빠르게 뽑기 위해서 만들어진 자료구조임.
• 완전 이진 트리 기반으로 만들어진 우선순위 중심의 자료구조이며, 우선순위 큐를 구현하기 위한 자료구조이다.
• 즉, 기준에 따라 우선순위를 정한 뒤 해당 우선순위에 맞춰서 꺼내기 위한 구조라고 볼 수 있음.
• 결과적으로 우선순위 큐를 구현하기 위해서 만들어진게 힙이기 때문에, 기본적인 큐의 규칙을 따르고 있음.
• 규칙: 힙의 트리 구조에서 중간에 데이터를 뽑을 수 없게 되어있는 등 이런 규칙이 존재함.

(2) 힙 - 추상 자료형

• 힙 객체: 부분적으로 정렬된 완전 이진트리로 부모노드는 자식노드 보다 우선순위가 높다.

[ 연산 ]

• 위에서 말한 것 처럼 우선순위 큐를 구현하기 위해 힙
• 우선순위 큐를 구현하기 위한 자료구조가 힙이기 때문에, 큐의 규칙을 따르게 됨.
• delete() 함수를 보면 힙(루트)에서 데이터를 삭제 할 수 있지, 중간 노드의 데이터를 삭제할 순 없음. ( Queue 규칙 )

(3) 힙 - 종류

[ 최소 힙 ]

• 루트 노드가 전체 노드 중에서 최소값인 힙을 의미한다.
• 트리의 모든 노드가 자식 노드보다 작은 값을 가진다.
• 트리의 레벨에 따라 데이터가 순서를 갖지는 않음. ( 같은 레벨에서 정렬 X )
• 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음.
• ( BST는 부모 보다 작은 값은 왼쪽 큰 값은 오른쪽 규칙이 존재, 최소 힙은 해당 안됨. )
• 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가짐. ( 단순히 부모보다 크면 됨 )
• 즉, 최소힙은 완전이진트리 + 자식은 부모보다 무조건 큰값 이러한 규칙이 존재하며, **작은 값을 우선순위**로 둔 방식임.

[ 최대 힙 ]

• 루트가 전체 노드 중에서 최대값인 힙을 의미한다.
• 최소 힙과 반대로, 트리의 모든 노드가 자식 노드보다 큰 값을 가진다.
• 트리의 레벨에 따라 데이터가 순서를 갖지 않음. ( 최소 힙과 동일함 )
• 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한이 따로 없음
• 루트가 가장 큰 값을 갖고 자식은 부모보다 작은 값을 가져야 한다.
• 즉, 완전이진트리 구조를 가지며, **큰 값을 우선순위** 로 둔 방식임.

(4) 힙 - 힙이 아닌 경우

• 완전 이진 트리 구조를 가지고 있지 않으면 힙이 아님.
• 최소 힙 & 최대 힙에 해당하는 구조에서 우선순위에 해당하는 값이 올바른 위치에 없으면 힙이 아님.
• 즉, 최소 힙은 우선순위가 작은 값이므로, 작은 값으로 내려가야함 ( 부모가 자식 보다 작아야 함 )

(5) 힙 - 힙인 경우

• 첫 번째 이진 트리는 우선순위가 적용이 되어있지 않으므로, 힙이라고 볼 수 없음.
• 두 번째 이진 트리는 완전 이진 트리 이면서, 최소 힙을 구현한 모습으로 힙이라고 볼 수 있음.
• 세 번쨰 이진 트리 또한, 완전 이진 트리 모습이며 최소 힙을 구현한 모습으로 힙임.

---

✅ 3. 힙에서 삭제 및 삽입 연산

(1) 배열을 이용한 힙의 구현

• 완전 이진 트리이기 때문에 배열로 구현해도 기억장소 낭비가 없음
• 배열을 이용해서 힙을 구현하면 완전 이진 트리이기 때문에 배열로 구현해도 기억장소 낭비가 없음.

( 포인터를 쓰지 않고 인덱스 만으로 계산해서 구할 수 있어서 실행속도 면에서 효율적임. )
완전 이진 트리 배열 : [1, 15, 5, 20, 16, 10, 19, 25, 30 ... ]
             index : [0,  1, 2,  3,  4,  5,  6,  7,  8 ... ]
왼쪽 자식 노드: 1(index) * 2 = 2(index)
오른쪽 자식 노드 : 1(index) * 2 + 1 = 3(index)
** 완전이진트리는 2의 배수씩 커지는 경향이 있음.**

• 즉, 완전 이진 트리를 기반이라, 배열에 낭비되는 메모리 셀이 존재하지 않는다는 의미임.
• 또한, 연결 리스트 보다 실행 속도 면에서 효율적임.
• 이유는, 포인터를 따라서 이동하는것이 아니라, 인덱스 계산을 통해 자식의 값을 추출하기 때문임.
• 즉, 힙은 위와 같은 장점 때문에 일반적으로는 배열로 구현을 하게 됨.

(2) 힙 - 루트 노드 삭제

• 힙은 Queue 자료구조의 규칙을 따르기 때문에 반드시 루트에서 삭제가 되어야 함.
• 다른 B-Tree 나 여러 Tree 구조는 중간에서 삭제가 되지만, Queue 를 구현하기 위한 힙이기 때문임.

[ 구조체 및 함수 선언부 ]

• (1) typedef struct heap: 힙을 표현하기 위한 구조체 정의이며, MAX_SIZE 는 힙의 요소들을 저장할 배열이다. 또한, size 필드는 힙에 현재 저장된 요소의 개수를 의미한다.
• (2) child, parent 변수: 힙을 재정렬 할 때 사용하는 부모 노드와 자식 노드의 인덱스를 저장할 변수이며, 1과 2로 초기화
• (3) data = h -> heap[1]: 해당 변수에는 현재 h -> heap[1] 즉, 배열의 인덱스 제일 첫 번째 요소가 들어가게 됨.
• (4) temp = h -> heap[(h -> size)--]: 해당 변수에는 현재 배열의 size 를 넣게 되는데, 결국 마지막 요소를 넣는것임.
• 정리하면, 힙의 첫 번째 인덱스와 끝의 인덱스를 구해서 초기화를 해주는 로직임. ( 즉, 배열의 첫 번째와 끝 index )

[ 삭제 및 재정렬 로직 ]

• (1) while(child <= h -> size): child 인덱스가 힙의 실제 크기인 h -> size 보다 작거나 같은 동안, 즉 비교할 자식 노드가 하나라도 있는 동안 루프를 반복함.
• (2) child < h -> size: 해당 조건은 오른쪽 자식(child+1) 이 존재하는지 확인을 함.( 왼쪽 자식만 있을 수도 있으니까 )

(3) h -> heap[child] > h -> heap[child+1]) { child++; }:

• 현재 힙 배열에서 왼쪽 자식 & 오른쪽 자식 비교를 하고 왼쪽 자식이 오른쪽 자식보다 클 경우 child++ 를 해줌.
• 현재 15 > 5 를 비교하게 되므로, true 즉, child++; 를 하게 됨. child == 3 이 된 상태임.

(4) if(temp <= h->heap[child]) break

temp = heap[lastIndex]; -> temp -> 23
temp <= heap[child]; -> 23 <= 3 [false]
break; -> 마지막 인덱스 temp 가 현재 heap[child] 인 자식이랑 같거나 작을 경우 반복문 탈출함.

• 현재 temp 는 23 이고 heap[child] 는 5이다. 23 <= 5 이므로, false 즉, break; 문을 수행하지 않음.
• 또한, heap[parent] = heap[child] 를 통해서 
• parent 는 1이고, heap[parent] 는 결국 heap[1] 루트를 의미한다. 여기서 heap[parent] = heap[child] 를 하게 되면 루트 노드에 child 의 값을 넣게 되는 것이다. 즉, 루트에는 위와 같이 5가 들어가게 된다.
• 최종적으로, parent = child 값을 넣음으로써, 다음 반복문 때 parent 는 3 index 를 가지고 시작하는 것임.
• 마지막으로 child *= 2; 를 함으로써, child 의 값을 6으로 올리게 되며, child 인덱스는 10이 됨.
• 결국 이러한 과정을 반복문을 통해서 size 만큼 계속 돌리게 됨.
• (8) h->heap[parent] = temp: 루프가 끝난 parent 위치가 temp 값이 최종적으로 자리 잡을 곳임. 여기에 temp 값을 넣음.
• (9) return data: 가장 처음에 저장해두었던 힙의 원래 최소값(data)을 반환

[ 삭제 연산 예시 ]

        1
      /   \
    10      2
   /  \
  20   30

• 최소힙을 예시로 들면, 맨 위의 루트 노드를 삭제하면서 반환을 하게 됨.

        30
      /   \
    10      2
   /  
  20

• 이후, 완전 이진 트리의 배열 마지막 부분인 30을 루트로 올리게 됨.
• 이때 마지막 인덱스 부분의 노드는 삽입 때 이미 최소힙 기준으로 삽입이 되어서 들어간거라 부모보다 큼.
• 이후, 루트 노드와 아래 자식 노드 10, 2 와 비교 후 최소힙이므로 더 작은 자식과 자리를 바꾸게 됨.

        2
      /   \
    10      30
   /  
  20

• 그러면, 위와 같은 구조가 되게 되며, 2 < 10, 2 < 30 이므로 더 이상 내려갈 필요가 없어짐. ( 최종 결과 )

[ 삭제 연산 정리 ]

• (1) 가장 작은 값(루트)을 일단 다른 곳에 백업을 미리 해둠 (해당 값을 반환해줘야 하므로 최종적으로 변수에 담아 반환함.)
• (2) 힙의 가장 마지막 노드를 루트 자리(1번 인덱스)로 강제로 가져옴.
• (3) 힙의 전체 크기를 1 줄임.
• (4) 루트 자리로 온 새 노드는 힙의 다른 값들보다 클 확률이 높음. (최소 힙 규칙 위반)
• (5) 이 노드를 자신의 자식 노드들과 비교하며 아래로 내려보내게 됨.
• (6) **두 자식 중 더 작은 값**과 자신을 비교해서, 자신이 더 크면 자리를 바꿈.
• (7) 제자리(자식들보다 작거나 같아지는 위치)를 찾거나, 힙의 맨 끝(리프 노드)에 도달할 때까지 이 과정을 반복하게 됨.

(3) 힙 - 노드 삽입 연산

• 해당 코드는 최소 힙에 새로운 원소를 삽입하는 함수 코드이다.
• 동작 원리는 새 데이터를 힙의 가장 마지막에 추가한 뒤, 부모 노드와 비교하여 제자리를 찾아 올라가는 방식임.
• (1) 새 데이터를 힙의 가장 마지막 위치(배열의 맨 끝)에 일단 삽입을 함.
• (2) 삽입된 노드가 자신의 부모 노드보다 작다면, 최소 힙의 규칙을 어기게 됨.
• (3) 이때, 부모 노드와 자리를 바꾸게 됨.
• (4) 새 데이터가 제자리(부모보다 크거나 같아지는 위치)를 찾거나, 힙의 루트(꼭대기)에 도달할 때까지 이 과정을 반복함.
• 삽입 하는 연산은 아래에서 위로 올라가는 과정이라 "up-heapify" 으로 부르며, 반대로 삭제하는 과정은 위에서 아래로 제자리를 찾아 내려가는 과정으로 "down-heapify" 이라고 부른다.
• 결론은, 삽입 연산은 마지막 위치에 데이터를 삽입하고 비교를 하면서 제자리를 찾아가는 원리임.

[ 삽입 연산 예시 ]

        2
      /   \
    10      30
   /  
  20

• 위와 같이 기존 최소힙이 존재하고, 새 값으로 "1" 을 추가한다고 가정을 하겠음.

        2
      /   \
    10      30
   /  \
  20    1

• 새 값 "1" 은 먼저 배열의 인덱스 맨 마지막에 추가가 되게 됨.
• 완전이진트리 규칙을 지키기 위해서 가장 마지막 위치에 삽입이 되는 것임.

        2
      /   \
     1      30
   /  \
  20   10

• 이후, 부모와 비교하며 위로 올라가게 됨. ( 최소힙 조건 : 부모보다 작으면 올라감 )
• 즉, 새 노드 1의 부모는 10이고 최소힙 조건으로 1 < 10 true 이기 때문에 변경됨.

        1
      /   \
     2      30
   /  \
  20   10
최종 배열: [1, 2, 30, 20, 10]

• 부모 노드인 루트 노드 보다도 작기 때문에 추가 된 "1" 은 결국 루트 노드로 올라가게 됨. ( up-heapify )
• 즉, 새로운 노드를 추가할 시 위와같은 과정을 거치면서 추가 된 숫자가 올라가게 됨.up-heapify
• 루트까지 올라가거나 추가 된 데이터의 부모 노드 데이터가 더 작을 때 까지 반복하게 됨.