힙과 우선순위 큐 : 제일 큰 값, 작은 값
이번 포스트에서는 특정 시나리오에서 유용하게 사용될 수 있는 트리 자료구조의 카테고리에 있는 힙 (Heap)에 대해 알아보도록 하겠습니다.
힙은 데이터 셋에서 가장 큰 또는 가장 작은 데이터 원소를 계속 알고 있어야 할 때 유용하게 쓰입니다.
또 힙의 기능을 제대로 파악하기 위해 우선순위 큐 (Priority queue) 또한 함께 알아보도록 하겠습니다.
1. 우선순위 큐 (Priority queue)란?
일반 큐 (Queue)는 FIFO (First-In, First-Out)로 항목을 처리하고 자료구조의 양끝에서만 데이터를 처리합니다.
큐의 데이터에 접근하려면 데이터의 삽입된 순서에 우선권이 있습니다.
스택과 큐 - 제약을 통한 문제 해결 전략
이번 포스팅에서 효율성 보다 코드의 간결함에 중점을 둔 자료구조에 대해 알아보겠습니다. 스택과 큐는 임시데이터를 처리할 수 있는 도구입니다. 임시데이터란 사용 후에는 의미 없는 데이터
hy1as.tistory.com
우선순위 큐 (Priority queue)에서 삭제와 접근은 전형적인 큐와 유사합니다.
다른 점은 삽입이 이루어질 때 데이터를 늘 특정 순서대로 정렬시킵니다.
우선순위 큐는 추상 데이터 타입의 한 예입니다.
이는 보다 기초적인 자료구조로 구현할 수 있다는 것을 의미합니다.
정렬 상태를 유지하기 위해 정렬된 배열을 이용해 보겠습니다
대신에 몇 가지 제약사항이 추가됩니다.
- 데이터를 삽입할 때 항상 적절한 순서를 유지합니다.
- 데이터는 배열 끝에서만 삭제합니다.(배열 끝을 우선순위 큐의 앞으로)
정렬된 배열로 실제 구현 시 매우 쉽게 구현할 수 있습니다.
그렇다면 효율성은 어떨까요?
- 삭제 : 배열 끝에서 삭제 -> $ O(1) $
- 삽입 : 정렬된 상태를 유지하기 위해 모든 내부 원소 탐색 및 삽입 위한 시프트 -> $ O(N) $
삭제는 매우 빠르게 이뤄지지만 삽입 연산이 꽤 느립니다.
더 효율적인 방법은 없을까요?
여기서 더 적합한 자료구조가 바로 힙 (Heap)입니다.
2. 힙 (Heap)
힙에도 몇 가지 종류가 있지만 이 포스트에서 얘기할 힙은 이진 힙 (Binary heap)입니다.
이진 힙은 특수한 종류의 이진트리입니다.
이진트리는 각 노드에 최대 자식이 둘인 트리입니다.
이진 탐색 트리 : 검색, 삽입, 삭제 모두 O(logN)
데이터를 특정 항목을 기준으로 정렬하고 싶을 수 있습니다. 퀵 정렬 알고리즘과 같은 방법으로 정렬을 할 수 있겠지만 정렬에는 비용이 발생합니다. 또 정렬된 자료구조에서 데이터의 변경이
hy1as.tistory.com
이진 힙에는 최대 힙 (max-heap)과 최소 힙 (min-heap)으로 두 가지 종류가 존재합니다.
힙은 다음의 조건을 따르는 이진트리입니다.
- 각 노드의 데이터는 자신의 모든 자손 노드의 데이터 보다 커야 한다 ( 힙 조건, heap condition )
- 트리는 완전(complete) 해야 한다.
완전해야 한다는 조건이 의미하는 것이 무엇일까요?
완전 트리란 트리에 빠진 노드 없이 노드가 완전히 채워진 트리를 뜻합니다.
각 레벨을 왼쪽에서 오른쪽으로 읽었을 때 빈 공간이 없어야 합니다.
바닥에는 빈 공간이 존재할 수 있는데, 여기서 빈자리의 오른쪽으로 어떠한 노드도 없어야만 합니다.
3. 힙 속성
이진트리는 검색하기 위한 값이 주어졌을 때 두 자손 중 왼쪽 자손 방향으로 가야 할지 오른쪽 자손 방향으로 가야 할지 알 수 있습니다.
하지만 힙은 주어진 값이 내 자손에 존재하는지 정도만 확인할 수 있습니다.
우리는 이것을 "힙은 이진 탐색 트리에 비해 약한 정렬 (Weakness ordered)"라고 합니다.
자손이 조상보다 클 수 없다는 분명한 순서가 존재하지만 값을 검색하기에는 부족합니다.
힙 내에서 가장 우선순위가 높은 것 (최대 힙 - 최댓값)은 루트 노드입니다.
위와 같은 속성 때문에 연산 구현시 삽입, 삭제는 구현하지만 검색은 보통 구현하지 않습니다.
연산 구현에 있어 마지막 노드 (Last node)란 개념이 필요합니다
마지막 노드는 바닥 레벨에서 가장 오른쪽에 위치한 노드입니다.
4. 힙 삽입
힙 삽입은 다음과 같은 단계로 진행됩니다.
- 새 값의 노드를 생성하고 마지막 노드로 삽입 (완전한 상태 유지)
- 새로 삽입한 노드와 부모 노드 비교
- 새로 삽입한 노드가 부모 노드보다 크면 스왑 (Swap)
- 새 노드보다 큰 부모 노드를 만날 때까지 1~3 단계 반복
부모를 따라 올라가기 때문에 시간 복잡도는 레벨 수만큼인 $ O(logN) $ 이 나오게 됩니다.
연산 구현에 있어 마지막 노드 (Last node)란 개념이 필요합니다
마지막 노드는 바닥 레벨에서 가장 오른쪽에 위치한 노드입니다.
그렇다면 마지막 노드는 어떻게 찾을 까요?
아쉽게도 지금은 모든 노드를 탐색하는 방법 밖에 없습니다.
뒤에서 마지막 노드를 찾기 이슈에 대한 해결책을 알아보도록 하겠습니다.
5. 힙 삭제
힙에서 값 삭제는 루트 노드만 가능하다는 것을 인지하고 진행해야 합니다.
- 마지막 노드를 루트자리로 값 복사 (루트 노드 삭제)
- 덮어씌워진 루트 노드를 적절한 자리까지 아래로 트리클링(Trickling)
트리클링이란 어떻게 진행할까요?
- 트리클 노드의 두 자식을 확인해 어느 쪽이 큰지 확인
- 트리클 노드가 두 자식 노드 중 큰 노드보다 작으면 큰 노드와 트리클 노드를 스왑
- 트리클 노드에 그 노드보다 큰 자식이 없을 때까지 1~2 단계 반복
두 자식 중 큰 노드와 스왑 해야만 트리의 정렬이 망가지지 않습니다.
삭제 역시 레벨만큼의 단계가 진행되기에 시간 복잡도는 O(logN)이 나오게 됩니다.
5. 마지막 노드 문제
앞서 삽입 연산 시 발생하는 마지막 노드 이슈에 대해 언급했었습니다.
우선 왜 마지막 노드에 삽입해야만 할까요?
마지막 노드에 삽입하지 않을 시 트리의 완전한 상태는 깨지고 불균형한 트리가 됩니다.
트리의 불균형도가 높아질수록 레벨이 많아지는 트리의 형태가 나올 가능성이 높아지게 됩니다.
이는 효율성을 떨어트리게 됩니다.
그래서 효율성을 위해 힙은 완전한 트리로 구현돼야 합니다.
마지막 노드 찾기 이슈는 어떻게 해결해야 할까요?
바로 힙을 배열로 구현하면 됩니다.
이렇게 구현을 하게되면 노드들이 배열 내에서 일정한 패턴을 보이며 저장됩니다.
마지막 노드는 항상 배열의 가장 뒤 원소로 위치합니다.
이제 힙을 코드로 구현해 보겠습니다.
앞서 연산 설명에서 언급했듯이 삽입과 삭제를 위해서는 힙을 트리클링 할 수 있어야 합니다.
그리고 트리클링은 부모나 자식에 접근해서 순회가 가능해야 합니다.
배열 인덱스만으로 노드에서 노드로 어떻게 이동할까요?
위에서 말한 패턴을 이용하면 됩니다
배열 내에서 다음과 같은 특성을 가지고 있습니다.
- 어떤 노드의 왼쪽 자식을 찾으려면 $ (index * 2) + 1 $ 공식을 사용한다.
- 어떤 노드의 오른쪽 자식을 찾으려면 $ (index * 2) + 2 $ 공식을 사용한다.
- 어떤 노드의 부모를 찾으려면 $ (정수)(index - 1) / 2 $ 공식을 사용한다.
이러한 특성을 이용해 연산을 코드로 구현해 보겠습니다.
class Heap {
data
constructor() {
this.data = []
}
// 루트 노드
getRootNode() {
return this.data[0].length === 0 ? null : this.data[0]
}
// 마지막 노드
getLastNode() {
return this.data[0].length === 0 ? null : this.data[this.data.length -
1]
}
// 왼쪽 자식 인덱스
getLeftChildIndex(index) {
return index * 2 + 1
}
// 오른쪽 자식 인덱스
getRightChildIndex(index) {
return index * 2 + 2
}
// 부모 인덱스
getParentIndex(index) {
return Math.floor(index - 1) / 2
}
insertNode(value) {
// 마지막 노드로 삽입
this.data.push(value)
// 삽입된 노드의 인덱스
let newNodeIndex = this.data.length - 1
// "위로 트리클링" 진행
//새 노드가 루트 자리에 없고
//새 노드가 부모 노드보다 크면
while (newNodeIndex > 0 &&
(this.data[newNodeIndex] >
this.data[this.getParentIndex(newNodeIndex)])) {
// 새 노드와 부모 노드 교환
const temp = this.data[this.getParentIndex(newNodeIndex)]
this.data[this.getParentIndex(newNodeIndex)] = this.data[newNodeIndex]
this.data[newNodeIndex] = temp
// 새 노드의 인덱스 업데이트
newNodeIndex = this.getParentIndex(newNodeIndex)
}
}
deleteNode() {
// 힙에서는 루트노드만 삭제하므로
// 배열에서 마지막 노드를 팝해 루트노드를 덮어 씌움
this.data[0] = this.data.pop()
// "트리클 노드" 인덱스 저장
let trickleNodeIndex = 0
// "아래로 트리클링"
// 트리클 노드에 자신보다 큰 자식이 있으면
while (this.hasGreaterChild(trickleNodeIndex)) {
// 더 큰 자식의 인덱스를 변수에 저장
const largeChildIndex = this.calculateLargerChildIndex(trickleNodeIndex)
// 트리클 노드와 더 큰 자식 스왑
const temp = this.data[largeChildIndex]
this.data[largeChildIndex] = this.data[trickleNodeIndex]
this.data[trickleNodeIndex] = temp
// 트리클 노드 인덱스 업데이트
trickleNodeIndex = largeChildIndex
}
}
hasGreaterChild(index) {
// 노드의 왼쪽이나 오른쪽 자식 중 index의 노드 값의 크기보다 큰 노드가 있는지 확인
return (this.data[this.getLeftChildIndex(index)] !== undefined &&
(this.data[this.getLeftChildIndex(index)] > this.data[index])
|| this.data[this.getRightChildIndex(index)] !== undefined &&
(this.data[this.getRightChildIndex(index)] > this.data[index]))
}
calculateLargerChildIndex(index) {
// 오른쪽 자식이 없으면
// 왼쪽 자식의 인덱스 반환
if (this.data[this.getRightChildIndex(index)] === undefined ||
this.data[this.getRightChildIndex(index)] === null) {
return this.getLeftChildIndex(index)
}
// 오른쪽 자식의 값이 왼쪽 자식 값보다 크면
// 오른쪽 자식 인덱스 반환
if (this.data[this.getRightChildIndex(index)] >
this.data[this.getLeftChildIndex(index)]) {
return this.getRightChildIndex(index)
} else {
// 왼쪽 자식의 값이 오른쪽 자식 값보다 크거나 같으면
// 왼쪽 자식 인덱스 반환
return this.getLeftChildIndex(index)
}
}
}