이진 탐색 트리 말고 다른 트리 종류도 많다. 모든 자료 구조가 그렇듯이 각 트리 종류마다 장단점이 있고 특정 상황에서 어떤 종류를 활용해야 할지 아는 것이 중요하다.
이번에는 특정 시나리오에 유리하게 활용할 수 있는 트리 자료 구조 중 하나인 '힙'을 알아본다. 힙은 데이터 세트에서 가장 큰 또는 가장 작은 데이터 원소를 계속 알아내야 할 때 굉장히 유용하다.
힙의 기능을 파악하기 위해선 '우선순위 큐'부터 살펴봐야 한다.
15. 1 우선순위 큐
지난번 배웠던 큐는 First In, First Out(FIFO) 방식으로 항목을 처리하는 리스트였다. 따라서 큐 끝에서만 데이터를 삽입하고 큐 앞에서만 접근과 삭제를 수행할 수 있다. 즉 데이터가 삽입됐던 순서에 접근 우선권이 있다.
'우선순위 큐(priority queue)'는 삭제와 접근에 있어 전형적인 큐와 흡사하나, 삽입에 있어 정렬된 배열과 비슷한 리스트다. 우선순위 큐는 앞에서만 데이터에 접근하고 삭제하는데, 데이터를 삽입할 때는 데이터를 늘 특정 순서대로 정렬시킨다는 특징을 가진다.
우선순위 큐는 병원 응급실의 중증도 분류체계 프로그램에서 사용된다. 응급실에서는 도착한 순서가 아니라 중증도를 따져 치료한다. 치명상을 입은 환자라면 약한 증상의 환자가 더 일찍 도착했더라도 그 중환자를 큐 맨 앞에 놓는다.
중증도 분류체계에서 환자 중증도를 1부터 10의 등급으로 매겨보자. 10이 가장 위험한 상태다.
갑자기 중증도가 3인 다음 환자가 도착하면 "처음부터" 이 환자를 우선순위 큐 내 적절한 위치에 넣는다.
우선순위 큐도 '추상 데이터 타입'의 한 예라서 기초적인 다른 자료 구조로 구현할 수 있다. 따라서 간단하게 '정렬된 배열'을 이용 가능하다. 배열을 사용하되 다음의 제약을 가진다.
- 데이터를 삽입할 때 항상 적절한 순서를 유지한다.
- 데이터는 배열의 끝(큐의 앞)에서만 삭제한다.
우선순위 큐의 주요 연산은 '삭제'와 '삽입'이다.
배열 앞에서 삭제는 인덱스 0에 생긴 빈자리를 메우기 위해 모든 데이터를 시프트 해야 하므로 O(N)이다. 하지만 배열 '끝'을 우선순위 큐 '앞'으로 삼았다. 이렇게 하면 항상 배열 끝에서 삭제하니 O(1)이다. 삭제에선 효율적이다.
삽입은 어떨까?
정렬된 배열에 삽입은 새 데이터를 넣을 자리를 알아내기 위해 배열 원소 N개를 모두 확인해야 하니 O(N)이었다.
따라서 배열 기반 우선순위 큐는 삭제가 O(1), 삽입이 O(N)이다. 우선순위 큐에 항목이 많아지면 삽입에서 원치 않은 지연이 발생할 수 있다.
그래서 우선순위 큐에서 보다 효율적인 기반의 자료 구조를 찾았다. 그것이 바로 '힙'이다.
15. 2 힙
힙에는 몇 가지 종류가 있다.
여기선 '이진 힙(binary heap)'을 다룬다.
이진 힙은 특수한 종류의 '이진 트리'다. (이진 트리는 각 노드에 최대 자식 노드가 둘인 트리였다)
이진 힙에도 '최대 힙(max-heap)'과 '최소 힙(min-heap)'이라는 두 종류가 있다. 둘 간에 큰 차이는 없다.
힙은 다음 조건을 따른다.
▶ 각 노드의 값은 그 노드의 모든 자손 노드의 값보다 커야 한다. 이 규칙을 '힙 조건(heap condition)'이라 부른다.
▶ 트리는 완전(complete)해야 한다.
'힙 조건(heap condition)'이란, 각 노드의 값이 그 노드의 모든 자손 노드보다 커야 한다는 뜻이다.
예를 들어 다음 트리에서 각 노드는 그 자손보다 크므로 힙 조건을 만족한다.
이진 탐색 트리에서 각 노드의 오른쪽 자식은 그 노드보다 컸다는 점에서 힙과 차이가 있다. 힙에서 노드는 그 노드의 모든 자손보다 '커야 한다'. 그래서 "이진 탐색 트리로는 힙을 만들 수 없다". 그리고 이것을 '최대 힙'이라고 부른다.
정반대의 힙 조건으로, 각 노드가 자손보다 '작은' 값을 갖도록 힙을 구성할 수도 있다. 이러한 힙을 '최소 힙'이라 부른다. 궁극적으로 최대 힙을 쓰든 최소 힙을 쓰든 차이는 미미하다. 두 힙은 힙 조건만 반대일 뿐 그 밖에 모든 면에서 동일하기 때문이다.
"트리가 완전해야 한다"는 두 번째 힙 규칙인 '완전 트리(complete tree)' 조건은 빠진 노드 없이 노드가 완전히 채워진 트리다. 따라서 트리의 각 레벨을 왼쪽부터 오른쪽으로 읽었을 때 모든 자리마다 노드가 있어야 한다.
하지만 바닥 줄에는 빈자리가 있을 수 있다. 단 빈자리의 오른쪽으로 어떤 노드도 없어야 한다.
이 트리는 트리의 각 레벨이 노드로 완전히 채워져 있으므로 완전하다.
위 트리는 세 번째 레벨에 한 노드가 빠졌으므로 완전하지 않다.
위 트리는 바닥 줄에 빈 자리가 있으나, 빈자리의 오른쪽으로 어떤 노드도 없으므로 완전하다.
각 노드가 자손보다 크고, 트리가 완전하므로 유효한 힙이다. 바닥 줄에 빈자리가 있으나 트리 오른쪽에만 국한되어 문제가 없다.
15. 3 힙 속성
힙 조건에 따라 힙은 특정 방식으로 정렬되지만, 이러한 정렬은 힙에서 값을 검색하는 데 전혀 도움이 안 된다.
이진 탐색 트리는 각 노드의 왼쪽과 오른쪽에 따라 값의 크기 차이가 있기에 검색이 용이했다. 그러나 힙은 왼쪽 자손과 오른쪽 자손 중 어느 쪽을 검색해야 할지 모른다.
따라서 힙은 이진 탐색 트리에 비해 '약한 정렬(weakly ordered)'이라고 말한다. 자손이 조상보다 클 수는 없지만, 값을 검색하기에는 부족하다.
힙에는 루트 노드가 항상 최댓값이라는 특성도 있다(최소 힙에서는 항상 최솟값이다). 이 점 때문에 힙이 우선순위 큐를 구현하는 훌륭한 도구가 될 수 있다. 우선순위 큐에서는 항상 가장 큰 우선순위를 갖는 값에 접근하려 한다. 힙에서는 항상 루트 노드다. 다시 말해 루트 노드가 가장 높은 우선순위를 갖는 항목에 해당한다.
힙의 주요 연산은 '삽입'과 '삭제'다. 힙에서의 검색은 모든 노드를 검사해야 하므로 대개 검색 연산을 구현하지 않는다.
힙에는 '마지막 노드(last node)'가 있다. 힙의 마지막 노드는 "바닥 레벨에서 가장 오른쪽에 있는 노드"다.
15. 4 힙 삽입
힙에 새 값을 삽입하려면 다음 알고리즘을 수행한다.
1) 새 값을 포함하는 노드를 생성하고, 바닥 레벨의 가장 오른쪽 노드 옆에 삽입한다. 이 값이 힙의 마지막 노드가 된다.
!!!! (힙의 주의 사항은 트리가 항상 '완전'해야 한다는 것이다. 즉, 빈자리의 오른쪽에 노드가 없어야 한다)
2) 새로 삽입한 노드와 그 부모 노드를 비교한다. 만약 새 노드가 부모 노드보다 크면 새 노드와 부모 노드를 바꾼다.
3) 새 노드보다 큰 부모 노드를 만날 때까지 2단계를 반복하며 새 노드를 힙 위로 올린다.
새 노드를 힙 위로 올리는 과정을 노드를 위로 '트리클링(trickling)'한다고 표현한다. 때로는 오른쪽으로, 때로는 왼쪽으로 올라가지만 어쨌든 올바른 위치에 안착할 때까지 항상 위로 올라간다.
힙 삽입의 효율성은 O(logN)이다. 노드가 N개인 이진 트리는 약 log(N) 개 줄을 갖는다. 최악의 경우 새 값을 꼭대기 줄까지 트리클링해서 올려야 하므로 최대 log(N) 단계가 걸린다.
15. 5 마지막 노드 탐색
삽입을 하기 위해선 '마지막 노드'를 찾아야 한다. 컴퓨터는 어떻게 찾을까?
컴퓨터 눈에선 '루트 노드'만 보이고, 링크를 따라 자식 노드에 갈 수 있다. 근본적으로 힙에서 검색하기 불가능하듯이, 힙의 마지막 노드도 모든 노드를 검사해야만 한다.
15. 6 힙 삭제
힙에서 값을 삭제하려면 루트 노드만 삭제가 가능하다. 이는 가장 높은 우선순위를 갖는 항목만 접근하고 삭제하는 우선순위 큐의 동작 방식과 일치한다.
힙의 루트 노드 삭제 알고리즘은 다음과 같다.
1) '마지막 노드'를 루트 노드 자리로 옮긴다. 결과적으로 원래 루트 노드는 삭제된다.
루트 노드 100을 삭제하려면 마지막 노드를 루트에 덮어쓴다. 위 예제에선 마지막 노드가 3이기 때문에 3을 100이 있던 자리에 넣는다.
힙 조건이 깨져버렸다. 현재 3은 모든 자손보다 작아서 바로잡기 위해 힙 조건을 다시 만족할 때까지 3을 아래로 트리클링해야 한다.
노드를 아래로 트리클링할 때 내려갈 수 있는 방향이 둘이므로 아래로의 트리클링은 위로의 트리클링보다 조금 더 복잡하다. 아래로 트리클링하는 알고리즘은 다음과 같다.
- 부모 노드(트리클링 하려는 노드)의 두 자식을 확인해 어느 쪽이 더 큰지 본다.
- 부모 노드가 두 자식 노드 중 큰 노드보다 작으면 그 큰 노드와 스왑한다.
- 트리클링하려는 노드에 그 노드보다 큰 자식이 없을 때까지 1, 2단계를 반복한다.
3의 자식 노드엔 88과 25, 두 자식이 있었다. 둘 중 88이 더 크고, 3보다 크니깐 88과 스왑한다.
이제 3엔 87과 16 두 자식이 있다. 둘 중 87이 더 크고 87은 3보다 크므로 트리클 노드와 87을 스왑한다.
3의 자식은 현재 86과 50이다. 86이 더 크고 86은 트리클 노드보다 크니 86과 스왑한다.
여기까지 오면 트리클 노드에 자기보다 큰 자식이 없다. 힙 조건을 만족하므로 이제 끝이다.
만약 두 자식 중 더 작은 노드와 스왑하면 부모 노드는 자손 노드보다 항상 커야 한다는 힙 조건이 바로 깨진다. 그러므로 더 큰 노드와 스왑하는 것이다.
힙에서 삭제하려면 루트부터 시작해 log(N) 개 레벨을 거쳐 노드를 트리클링해야 하므로 삽입과 마찬가지로 시간 복잡도가 O(logN)이다.
15. 7 힙 vs 정렬된 배열
왜 힙이 '우선순위 큐'를 구현하는 훌륭한 방식인지 알아보자.
'정렬된 배열'의 경우, 엄청 빠르고 때로는 느린 자료 구조다.
하지만 '힙'은 일관되게 매우 빠른 속도를 자랑한다.
우선순위 큐는 일반적으로 삽입과 삭제를 거의 비슷한 비율로 수행한다. 삽입과 삭제, 둘 다 빨라야 하는데 어느 한 연산이라도 느리면 우선순위 큐는 효율성이 떨어진다.
따라서 우선순위 큐의 주요 연산인 '삽입'과 '삭제'를 매우 빠른 속도로 수행하려면 '힙'을 사용한다.
15. 8 다시 살펴보는 마지막 노드 문제
왜 힙에는 '완전성(completeness)'가 중요한지 알아보자.
삽입 시 새 값을 마지막 노드 옆이 아닌 곳에 넣으면 안 될까? 삭제할 때 루트 노드를 마지막 노드가 아닌 다른 노드와 대체할 수 없을까?
그 이유는 "균형 잡힌" 힙으로 유지하고 싶어서다. 만약 균형을 잡지 않고 멋대로 노드를 추가하면 트리에 불균형을 초래한다.
만약 계속 바닥 가장 왼쪽 자리에 새 노드를 삽입하면 불균형의 정도는 더 심해진다. 마찬가지 이유로 힙의 균형을 유지하기 위해 삭제 시 마지막 노드를 루트 노드로 넣는다.
이러한 균형이 중요한 이유는 O(logN) 연산을 유지하기 위해서다. 다음과 같이 불균형이 심한 트리는 순회에 O(N) 단계가 걸린다.
15. 9 배열로 힙 구현하기
어떤 힙에서든 노드 N개를 모두 순회하지 않고도 일관되게 '마지막 노드'를 찾는 알고리즘이 힙 연산의 핵심이다.
배열로도 힙을 구현할 수 있다. 즉 힙 자체가 내부적으로 배열을 사용하는 추상 데이터 타입일 수 있다.
배열로 구현하기 위해선 각 노드마다 배열의 인덱스를 할당한다.
여기엔 특정 패턴이 있다. 루트 노드는 항상 인덱스 0에 저장한다. 그리고 한 레벨 아래로 내려가 왼쪽에서 오른쪽 방향으로 진행하면서 각 노드마다 배열의 다음 인덱스를 할당한다. 레벨 끝에 도달하면 다음 레벨로 내려가 같은 패턴을 반복한다.
힙을 배열로 구현하는 이유는, 마지막 노드 문제를 해결하기 위해서다. 배열을 사용하면 "마지막 노드는 항상 배열의 마지막 원소"가 된다. 위 예제에선 3이 배열의 마지막 값이다.
마지막 노드가 항상 배열 끝이므로 아주 간단하게 마지막 노드를 찾을 수 있다. 마지막 원소에 접근하기만 하면 되기 때문이다. 뿐만 아니라 힙에 새 노드를 삽입할 때도 배열 끝에 삽입하면 새 노드가 마지막 노드가 된다.
힙 삽입과 삭제를 하려면 힙을 트리클링 할 수 있어야 한다. 하지만 각 노드의 링크를 따라갈 수 없는 '배열'로 저장되어 있기 때문에 다른 방식으로 힙 순회를 해야 한다. 여기엔 공식이 있다.
- 어떤 노드의 왼쪽 '자식'을 찾으려면 (index * 2) + 1 공식을 사용한다.
- 어떤 노드의 오른쪽 '자식'을 찾으려면 (index * 2) + 2 공식을 사용한다.
- 어떤 노드의 '부모'를 찾으려면 (index - 1) / 2 공식을 사용한다.
해당 공식을 통해 자식과 부모의 인덱스를 알 수 있고, 서로 연결할 수 있다.
물론 연결 리스트로도 구현할 수 있지만, 배열로 구현하는 것이 더 널리 사용된다. 배열로 이진 탐색 트리도 구현할 수 있지만, 힙은 마지막 노드를 쉽게 찾아준다는 점에서 배열로 구현하면 유리한 첫 이진 트리 사례다.
15.10 우선순위 큐로 쓰이는 힙
다시 말하지만 우선순위 큐는 가장 높은 우선순위를 갖는 항목에 '바로' 접근한다.
힙은 가장 높은 우선순위의 항목이 항상 루트 노드에 있으니 바로 접근할 수 있다. 가장 높은 우선순위의 항목을 처리할 때마다 다음으로 높은 우선순위 항목이 힙 꼭대기로 오면서 다음 처리할 준비를 갖춘다. 이 과정에서 힙은 삽입과 삭제를 모두 아주 빠른 O(logN)으로 처리한다.
여기서 힙의 약한 정렬이 굉장한 장점으로 작용한다. 완벽히 정렬할 필요가 없으니 새 값을 O(logN) 시간에 삽입할 수 있다. 동시에 항상 최댓값에 접근할 수 있을 만큼 정렬되어 있다.
그래서 우선순위 큐 구현에 힙이 적합하다.
15. 11 마무리
이진 탐색 트리는 삽입 비용을 최소화하며 빠르게 검색하고, 힙은 우선순위 큐를 만드는 완벽한 도구이다.
해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.
오로지 학습용으로 작성하였음을 밝힙니다.
더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.
'자료구조 & 알고리즘' 카테고리의 다른 글
| Ch.17 그래프로 뭐든지 연결하기 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.14 |
|---|---|
| Ch.16 트라이(trie)해 보는 것도 나쁘지 않다 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.13 |
| Ch.14 이진 탐색 트리로 속도 향상 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.10 |
| Ch.13 노드 기반 자료 구조 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.09 |
| Ch.12 속도를 높이는 재귀 알고리즘 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.09 |
