오늘 공부한 내용은 힙(Heap)이다. 이제 점점 낮선 자료구조들이 나오기 시작한다.
확실하게 이해하고 넘어가도록 해야겠다.
현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.
틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.
📌 개념
힙(Heap)은 그래프의 트리 구조 중 하나로 우선순위 큐를 구현하기 위해 만들어진 자료구조다.
우선순위 큐는 큐에 우선순위 개념을 접목시킨 것으로 데이터를 자유롭게 추가할 수 있지만, 꺼낼때는 우선순위가 높은 데이터를 먼저 꺼낸다.
힙을 비롯한 트리 구조에서 각 정점을 노드라고 부른다.
각 노드는 자식 노드를 2개씩 가질 수 있다. 또한 노드는 위에서 붜 채워지며 같은 층에서는 왼쪽 부터 채워진다.
위 그림은 힙의 예다. 각 노드에 적힌 숫자가 저장된 데이터이다.
위 힙은 최소 힙으로 가장 작은 수가 우선순위를 가진다.
힙(Heap)의 종류
가장 낮은 값이 우선순위를 가지는 최소 힙(Min Heap)과 가장 큰 값이 우선 순위가 되는 최대 힙(Max Heap)이 있다.
데이터 추가
최소 힙에서 데이터를 추가할 때 자식 노드의 값이 반드시 부모 노드의 값보다 커야 한다는 규칙이 있다.
따라서 맨 위의 노드는 제일 작은 값을 가지게 된다.
힙에 5를 추가해 보았다.
데이터를 넣을 때는 맨 아래층 왼쪽 부터 추가하기 때문에 빈자리인 7옆에 자리로 들어갔다.
이때 부모 노드가 자식 노드 보다 큰경우에는 우선 순위에 의해 부모와 자식을 교채한다.
부모는 6, 자식은 5 이기 때문에 교체를 실시한다.
5가 위로 올라가고 6이 아래로 내려왔다.
다음은 1과 비교할 차례다
부모 1, 자식 5는 부모인 1이 더 작기 떄문에 변경이 필요없다.
이렇게 데이터 추가가 완료 되었다.
데이터 삭제
힙에서 데이터를 꺼낼 때는 우선순위가 가장 높은 제일 위에 있는 데이터를 꺼낸다.
해당 예시에서 가장 우선순위가 높은 데이터인 1을 빼준다.
이제 가장 위의 있는 데이터가 빠졌기 때문에 힙의 구조와 노드를 재구성해야 한다.
힙의 마지막에 있는 노드를 제일 위로 옮긴다.
해당 예시는 6이 마지막에 있기 때문에 가장 위로 옮긴다.
그리고 다시 우선 순위를 탐색해 준다.
가장 작은 수가 우선 순위이다. 부모 6과 자식 3, 자식 5를 비교해준다.
부모6 > 자식5 > 자식3 이기 때문에 3과 6을 바꿔준다.
같은 과정을 한번 더 진행한다.
자식8 > 부모6 > 자식4 아기 때문에 4와 6을 바꿔준다.
이렇게 데이터를 꺼내는 작업이 완료 되었다.
이렇기 때문에 보관 중인 데이터의 최소값 혹은 최대값을 빈번하게 찾는 경우에 힙이 유용하게 사용된다.
나중에 공부할 다익스트라 알고리즘이 항상 최소값을 선택하는데, 이때 힙을 사용하기도 한다.
⏱️ 시간복잡도
힙은 항상 가장 작은 데이터가 맨 위에 있기 때문에 데이터 개수와 상관없이 O(1)의 시간 복잡도를 가진다.
데이터를 꺼낸 뒤 힙을 재구성할 때는 맨 끝에 있는 데이터를 맨 위로 옮긴 뒤 자식 노드와 비교하면서 밑으로 이동한다. 이 작업의 계산 시간은 트리의 높이에 비례한다. 데이터의 개수가 n이라면 힙의 높이는 log₂n이므로 시간복잡도는 O(log n)이 된다.
데이터를 추가도 마찬가지로 가장 끝에 데이터를 추가한 다음, 힙의 조건을 만족할 때까지 부모노드의 값과 비교하면서 위로 올라가기 때문에 시간복잡도는 트리의 높이에 비례하는, O(log n)이다.
참고 자료
그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠
[자료구조] 힙(heap)이란 : Heee's Development Blog https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
[자료구조] 힙[heap]이란? : bada308.log https://velog.io/@bada308/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99heap%EC%9D%B4%EB%9E%80
'CS 공부 > 자료구조' 카테고리의 다른 글
| [자료구조] 이진 탐색 트리 (Binary Search Tree) (1) | 2024.07.31 |
|---|---|
| [자료구조] 해시 테이블 (Hash Table) (2) | 2024.07.24 |
| [자료구조] 큐 (Queue) (0) | 2024.07.23 |
| [자료구조] 스택 (Stack) (1) | 2024.07.22 |
| [자료구조] 배열 (Array) (0) | 2024.07.17 |
