[자료구조] 9강 - 힙 — bin's Development Diary

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

[ 삭제 연산 예시 ]

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

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

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

[ 삭제 연산 정리 ]

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

(3) 힙 - 노드 삽입 연산

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

[ 삽입 연산 예시 ]

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

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

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

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

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

'방송통신대학교 > 🔢자료구조' 카테고리의 다른 글

[자료구조] 12강 - 멀티웨이 탐색 트리(1) (0)	2025.11.22
[자료구조] 11강 - BST, Splay, AVL, BB (0)	2025.11.20
[자료구조] 8강 - 스레드트리 (0)	2025.10.23
[자료구조] 7강 - 트리 (0)	2025.10.14
[자료구조] 6강 - 연결 리스트의 응용 (0)	2025.10.06