오늘은 Heap 이라는 자료구조에 대해 알아보자
Heap이란?
힙이란 완전 이진트리의 일종으로 반정렬 상태에 있다!
우선순위가 높은 노드가 위쪽에 있는 형태이고 이를 통해 최대값과 최소값을 빠르게 찾아낼 수 있도록 설계된 구조이다
그러면 Heap은 어디에 쓰이는가?
바로 우선순위 큐를 구현할 때 쓰인다.
사실상 힙이라는 구조는 우선순위 큐를 위해 존재한다고 봐도 무방하다!
우선순위 큐 구현에도 여러가지 방법(Array,LinkedList,Heap)이 존재하는데 Heap으로 구현하는 것이 가장 효율적이기 때문에 보통 우선순위큐는 heap으로 구현되어있다.
힙은 어떤 종류가 있을까?
힙은 최대힙과 최소힙 두가지 종류가 있다.
그림으로 보면 왼쪽이 최대힙으로 큰 값이 우선순위가 높아 제일 위에 있다.
오른쪽은 최소힙으로 작은 값이 위쪽에 위치하고 있는것을 볼 수 있다.
이처럼 힙은 부모노드는 자식 노드들보다 우선순위가 높다는 특징을 가지고 있다.(이 성질은 부분집합으로 뜯어봐도 성립하게 된다.)
그럼 삽입과 삭제는 어떻게 이루어 질까?
먼저 삽입에 대해 살펴보자
삽입은 제일 마지막 노드에 넣고 싶은 노드를 넣어주고 부모와 비교해 가면서 자기 자리를 찾는다.
그림으로 보면 새로운 노드가 제일 마지막에 들어가고 부모와 비교,또 비교해서 자기자리를 찾아가는 것을 볼 수 있다.
이것을 업힙(Up-Heap)이라고 한다.
삽입의 시간복잡도는 넣는데 O(1), 부모와 비교해 자기자리를 찾아가는데 O(log n)이 걸려 최종적으로 O(log n)이 걸린다.
그렇다면 삭제는 어떻게 이루어질까?
삭제를 하는경우는 우선순위가 제일 높은 노드를 추출하는 것이므로 루트 노드가 없어지게 된다.
루트노드를 추출하고 난 뒤, 삽입과는 반대로 제일 마지막에 있는 노드를 루트노드로 올려준다.
그리고 이번엔 자식과 비교해 자기자리를 찾아가게 된다.(마찬가지로 자식이 자신보다 우선순위가 낮아질때까지 반복한다.)
그림으로 보다시피 루트노드에 마지막 노드가 들어오고 자식과 비교해 자기 자리를 찾아간다.
이렇게 자식과 비교해 자리를 찾아내려가는 것을 다운힙(Down-Heap)이라고 한다.
시간복잡도는 O(log n)이 된다.
참고로 Heap Build라는 것이 있다.
힙빌드는 어떤 자료구조를 힙으로 만드는 행동을 말한다.
배열을 가지고 힙을 만들때의 시간복잡도는 O(n)이된다.
이는 업힙을 통해 구현하면 O(nlog n)이 되지만 다운힙을 통해 구현하면 O(n)이 되므로 다운힙을 통해 Heap Build를 하는것이 효율적이다.(이는 수학적인 증명이 포함되어 있어 넘어간다.)
추가로 이진힙과 이진 탐색트리를 비교해보자
이진힙
- 노드끼리의 상하관계를 보장하고 최소힙에서는 부모가 항상 자식보다 작다!!
이진탐색트리(BST)
- 좌우 관계를 보장하고, 부모는 왼쪽 자식보다 크고 오른쪽 자식보다 작거나 같다!
끝!
'Computer Science > 자료구조' 카테고리의 다른 글
| [자료구조] Stack과 Queue (0) | 2021.12.11 |
|---|---|
| [자료구조] Array와 List (0) | 2021.12.11 |
