힙(Heap)

Ouroboros·2023년 10월 29일

heap 자료구조 힙

1) 힙(Heap)의 개념과 특징

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
힙 트리에서는 중복된 값을 허용한다.
(이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

✨힙을 사용하는 이유

배열을 사용해서 최솟값이나 최댓값을 찾으면 Ο(n)만큼 시간이 걸린다. 하지만 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다.

2) 힙의 종류

최대 힙(max heap)
부모 노드의 키값 >= 자식노드의 키값
최소 힙(min heap)
부모 노드의 키값 <= 자식노드의 키값

✨힙 🆚 이진탐색트리

공통점
모두 완전 이진 트리이다.
차이점
- 힙은 최대/최소 검색을, 이진 탐색 트리는 탐색을 위한 구조이다.
- 최대힙은 각 노드의 값이 모두 자식 노드보다 크거나 같고, 최소힙은 각 노드의 값이 모두 자식 노드보다 작거나 같다. 즉, 힙은 왼쪽 노드의 값이 크든 오른쪽 노드의 값이 크든 상관 없다.
- 이진 탐색 트리는 각 노드의 왼쪽 자식은 더 작은 값으로, 오른쪽 자식은 더 큰 값으로 이루어져있다.

3) 힙의 동작

힙을 저장하는 표준적인 자료구조는 배열이다.
구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
힙에서의 부모 노드와 자식 노드의 관계
- 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
- 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
- 부모의 인덱스 = (자식의 인덱스) / 2

(1) 데이터 삽입

힙은 완전 이진 트리이기 때문에, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워진다.
채워진 노드의 위치에서, 부모 노드의 값보다 클 경우에는 부모 노드와 위치를 바꾸며 이를 반복한다.

1. 8을 삽입한다
2. 8과 4를 비교한다
3. 8이 더 크므로, 교환한다.
4. 8과 7을 비교하고, 8이 더 크므로 7과 교환한다.
5. 8과 9를 비교하고, 9가 더 크므로 더이상 교환하지 않는다.

(2) 데이터 삭제

최대 힙(Max Heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다. 반대로, 최소 힙(Min Heap)에서 삭제 연산은 최솟값을 가진 요소를 삭제하는 것이다. 따라서 루트노드를 삭제하는 것이다

1. 최대힙이라면 최대값을 가진 루트노드를 삭제한다.
2. 빈자리에 마지막 노드를 가져온다.
3. 3과 7을 비교하고, 7이 더 크므로 7과 3을 교환한다.
4. 3과 5를 비교하고, 5가 더 크므로 5와 3을 교환한다.