[코드잇-자료구조2 : 트리의 구조와 탐색] 2. 힙
본 게시물은 코드잇의(codeit) 자료구조 시리즈 강의 두번째 주제인 '트리의 구조와 탐색'을 듣고 정리한 게시물임을 알려드립니다.
- 강의 url : https://www.codeit.kr/topics/trees?mediumTypedId=UGxheWxpc3Q6NjZkZDU5YWI4OTg1YTI3ZWRkOTdlOWUz
트리의 구조와 탐색 - 알고리즘 · 자료구조 강의 | 코드잇
트리는 계층적 데이터를 효과적으로 표현할 수 있는 자료 구조입니다. 데이터가 서로 연결되어 있는 모습이 나무에서 가지가 뻗어 나간 모습과 비슷하다고 해서 트리라는 이름이 붙었죠. 트리
www.codeit.kr
1. 힙이란?
아래의 두 가지 조건을 모두 만족하는 트리
① 형태속성 : 힙은 완전 이진 트리이다.
② 힙 속성 : 모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 같다.
본 챕터에서는 힙을 활용하는 두 가지 방법을 알아볼 것 : CS의 가장 기본적이고 핵심적인 문제인 '정렬' 문제 해결, 유용한 추상 자료형인 '우선순위 큐' 구현하기
2. 정렬 문제
정렬 : 여러개의 데이터 요소들을 특정 순서로 재배치하는 것
ex. 오름차순, 내림차순
정렬 알고리즘 : 데이터를 재배치하는 구체적인 방법
ex. 삽입 정렬, 선택 정렬, 합병정렬, 퀵정렬, 힙 정렬(앞으로 우리가 할 것)
3. 배열로 구현한 힙
완전 이진 트리는 동적배열, 파이썬에서는 자료형 '리스트'를 이용해서 나타낼 수 있음 (지난 챕터)
힙도 완전 이진 트리이기에 보통 동적 배열로 나타낸다.
위와같이 형태 속성과 힙 속성을 만족하는 트리가 있을 때, 노드 위의 숫자들은 동적 배열의 인덱스를 나타냄.
- 즉, 파이썬의 리스트로 힙이 구현된 것
특정 인덱스가 주어졌을 때 부모와 자식 노드를 찾는 방법 (지난 챕터)
- 왼쪽 자식 인덱스 : 인덱스 * 2
- 오른쪽 자식 인덱스 : 인덱스 * 2 + 1
4. 힙을 만드는 방법 1
4절과 6절에서는 힙을 만드는 방법에 대해 상술
Before
- 위의 완전 이진 트리는 동적 배열로 구현했고, 노드 위의 정수들은 노드가 저장된 인덱스들임
- 마지막 레벨 빼고 다 채워져있고, 마지막 레벨이 왼쪽부터 채워져있으므로 형태 속성은 만족하지만 힙속성은 만족하지 않으므로 힙이라고 할 수 없음
힙 만들기 과정
힙 속성 만족시키지 않는 노드가 발견될 때마다 힙 속성 만족하도록 재배치
일반화 : heapify
파라미터로 어떤 노드를 하나 받는다.
이 노드를 부모 노드라고 할 때, 부모 노드, 왼쪽 자식, 오른쪽 자식 중 가장 큰 것을 고른다.
가장 큰 노드가 부모 노드가 아니라면 가장 큰 노드와 부모 노드를 바꿔준다.
기존의 부모 노드가 밑으로 갔는데 그 부모 노드가 또 힙 속성을 어긴다면 힙 속성이 충족될 때 까지 반복한다.
즉, 이렇게 heapify 알고리즘을 쓰면 원하는 노드를 힙 속성에 맞는 위치로 재배치 가능
시간 복잡도 분석
트리에 저장되어 있는 노드의 개수를 n이라고 할 때 이 알고리즘의 최악의 경우는 파라미터로 맨 위의 루트 노드를 넘겼는데 이게 계속 내려가서 결국 맨 밑의 리프 노드까지 내려가는 경우
- 이 때의 시간복잡도 : 최악의 경우 노드는 총 트리의 높이만큼 데이터를 비교하고 재배치시킨다. 힙은 완전 이진 트리이기 때문에 높이가 O(log(n))이다. 따라서 최악의 경우 heapify에 걸리는 시간은 O(log(n))에 비례하고, 그렇기에 시간 복잡도도 O(log(n))
- 즉, heapify 시간 복잡도 : O(lg(n))
5. [실습] heapify 함수 구현
6. 힙 만들기 2
- heapify : 파라미터로 넘기는 노드가 힙에서 위치를 찾아간다.
만약 heapify 함수에 노드 10부터 1까지 순서대로 넣어서 호출하면?
- 노드 10~6 : 리프 노드이기에 heapify를 해도 바뀌는 것은 없음
- 노드 5부터는 가정을 할수가 있는데, 노드 5를 뿌리로 하는 부분 트리의 노드들은 모두 힙 속성을 지키고 있다고 볼 수 있음
- 노드 10부터 3까지 heapify를 호출해 준 후 노드 2에 heapify를 호출할 차례가 왔다면, 호출 시 노드 2를 뿌리로 갖는 부분 트리는 이미 heapify를 호출했을 것이고, 그렇기 때문에 이 노드들은 이미 힙 속성을 지키고 있다고 확신할 수 있음
- 이제 루트 노드만 heapify를 호출해주면 되고, 이때도 마찬가지로 루트 노드에만 호출해주게 된다면 트리 안의 모든 노드들이 힙 속성을 지키고 있다고 확신할 수 있음
정리
- 완전 이진 트리가 위처럼 파이썬 리스트로 구현되어 있다면, 마지막 인덱스 부터 첫 인덱스까지 차례로 heapify를 적용하면 힙으로 만들 수 있음
시간 복잡도 분석
- 힙을 만들려면 heapify를 n개의 노드에 모두 호출해야 되고, 그러니까 O(log(n))이 n번 걸리는 것
- log(n)을 n번 곱하면 nlog(n)이니까, 힙을 만드는 데 걸리는 시간 복잡도는 O(nlog(n))
※ 트리 노드 n개일 때
7. 힙 정렬
힙 정렬이란?
- 힙 정렬 : 힙을 이용한 정렬 알고리즘
힙 정렬 과정
(오름차순)
- 힙속성 : 오름차순일때에는 부모 노드의 데이터가 자식 노드의 데이터보다 커야 한다.
(내림차순)
- 힙 속성을 반대로 바꾸고 똑같은 알고리즘을 적용하면 된다.
- 힙속성 : 내림차순일때에는 부모 노드의 데이터가 자식 노드의 데이터보다 작아야 한다.
힙 정렬 예제
1 단계 : 힙을 만든다.
- 위와 같은 힙이 있다고 가정하자
- 힙 속성 때문에 루트 노드인 14가 힙에서 가장 큰 노드
2단계 : root 와 마지막 노드를 바꿔준다.
- 루트 노드와 마지막 노드의 위치를 바꿔본다.
- 그러면 힙 속성이 망가진다.
(3단계. 바꾼 노드는 없는 취급을 한다.)
4단계. 새로운 노드가 힙 속성을 지킬 수 있게 heapify 호출
- 힙속성을 맞추기 위해서 루트노드에 heapify를 호출해준다.
- 단, 이 때 마지막 노드 인덱스 10은 이제 없는 인덱스 취급을 해준다.
- 이제 힙 속성 만족
2~4단계 반복(모든 인덱스 돌 때까지) : 인덱스 9랑 루트랑 바꾼다.
- 힙속성이 다시 망가짐
2~4단계 반복(모든 인덱스 돌 때까지) : 인덱스 8~2랑 루트랑 순차적으로 바꾼 후 heapify를 진행한다.
- 마지막으로 완성된 트리 (오름차순)
- 본 강의에서는 힙을 파이썬 리스트로 구현했고, 결국 아래와 같이 트리가 저장되어 있는 것.
8. [실습] 힙 정렬 구현하기
9. 힙 정렬 시간 복잡도 + 평가
10. 우선순위 큐
힙은 대표적으로 두가지 목적으로 사용됨
① 정렬 : 앞절들 내용
② 추상 자료형 '우선순위 큐'를 구현하기 위해 사용
추상 자료형
- 추상 자료형 : 내부적인 구현보다 기능에 집중하게 해주는 개념
※ 이전 강의인 자료구조 1 시간에 상세하게 다룬다.
우선순위 큐
- 큐, 스택과 같은 추상자료형이고, 선입선출인 '큐'와 비슷
- 데이터를 저장할 수 있고, 저장한 데이터가 우선순위 순서대로 나온다. (각 데이터마다 우선순위가 있음)
- 고객 문의 처리 시 불만도 높은 문의부터 처리할 때에와 같은 상황에서 활용됨
- 우선 빈 우선순위 큐를 생성
- 데이터 삽입 순서는 관계 없음
- 삭제할때에는 가장 큰 순서대로 삭제된다.
- 삭제되는 데이터가 리턴된다.
- 삭제대신 '추출'한다라고도 표현하기도 함
힙과 우선순위 큐
- 힙을 이용하면 '우선순위 큐'를 효율적으로 구현할 수 있음
11. 힙에 데이터 삽입하기
- 힙으로 우선순위 큐를 구현하기 위해서는 힙에 데이터를 삽입하고 삭제하는 방법을 알아야 한다.
힙에 데이터를 삽입하는 과정
예제
- 힙에 데이터 15를 삽입하려고 한다.
1단계. 힙의 마지막 인덱스에 데이터를 삽입한다.
- 15는 힙속성을 어기고 있는 상태
2단계. 삽입한 데이터와 부모 노드의 데이터를 비교한다.
3단계. 부모 노드의 데이터가 더 작으면 둘의 위치를 바꿔준다.
새로운 노드가 새 위치를 찾을 때까지 2~3단계 반복
- 15와 새로운 부모 노드 비교 후 자리 바꿈
- 15가 17보다 작으므로 위의 트리가 완성본
- 이런식으로 새로운 노드의 제자리를 찾는것
12. [실습] 힙 데이터 삽입 구현하기
13. 힙에서 최고 우선순위 데이터 추출하기
- 힙에서 가장 우선순위가 높은 데이터를 추출하는 방법
- 우선순위는 우리가 정하기 나름이며, 본 절에서는 가장 큰 데이터가 높은 우선순위를 갖는다고 가정
힙에서 최고 우선순위 데이터 추출하는 방법 (우선순위 = 가장 크기가 큰 숫자(root 노드)로 설정)
- 우선순위가 높은 데이터를 추출하면서 힙속성을 망가지지 않게 하는 메커니즘
예제
주어진 힙
1단계. root와 마지막 노드를 서로 바꿔준다.
2단계. 마지막 노드의 데이터를 변수에 저장해 준다.
3단계. 마지막 노드를 삭제한다.
4단계. root 노드에 heapify를 호출한 후 망가진 heap 속성을 고친다.
5단계. 변수에 저장한 최고 우선순위 데이터를 리턴한다.
14. [실습] 힙 우선순위 데이터 추출 구현
15. 힙 삽입, 추출 시간 복잡도