18 이진 힙

18.1 이진 힙

  이진 힙은 이진 검색 트리와 마찬가지로 트리의 한 종류이다. 그러므로 트리에 적용되는 규칙들이 다 동일하게 적용되지만 추가적으로 적용되는 규칙들이 있다. 힙에도 여러가지 종류가 있지만 지금 알아 볼 내용은 힙의 한 종류인 이진 힙이다. 이진 힙은 다시 최소 힙과, 최대 힙으로 구분된다. 

 

  최대 이진 힙에서는 부모 노드가 항상 자식 노드보다 큰 값을 가진다. 자식 노드로 저장되는 왼쪽/오른쪽의 순서는 상관없이 한 레벨 아래에 있는 즉, 자식 노드보다는 항상 부모 노드가 크다.(오른쪽/왼쪽 순서는 중요하지 않고 데이터를 저장할 때 왼쪽부터 값이 저장된다.)

 

  최소 이진 힙은 최대 이진 힙과 반대로 부모 노드는 항상 자식 노드보다 작은 값을 가진다. 자식 노드로 저장되는 왼쪽/오른쪽의 순서는 마찬가지로 중요하지 않다.

 

  이진 힙은 이진 검색 트리와 마찬가지로 각 노드는 언제나 최대 두 개의 자식 노드를 갖는다. 그리고 이진 힙은 언제나 최적의 용량을 갖는다. 그리고 부모 노드의 자식 노드가 연결 될 때에는 언제나 왼쪽 자식이 먼저 채워진다. 즉, 시빌링 관계에 있는 노드들 사이에서는 특별한 순서가 없다.

 

18.2 힙 정렬

  이진 힙의 구현은 보통 배열의 요소들을 트리 구조에 맞게 위치시켜 구현하게 된다. 

/* 최대 이진 힙의 구성
부모 노드는 항상 자식 노드 보다 커야한다
형제 노드들 사이의 순서는 상관 없다

[15, 10, 8, 9, 7, 2, 3]

        15
      /    \
    10      8
   /   \   /  \  
  9    7  2    3
  
  
*/

  위의 최대 이진 힙을 예시를 봤을때 부모 노드와 자식 노드와의 위치 관계에는 수학적 규칙이 존재한다.

- 자식 노드 인덱스 = 2n + 1(왼쪽 자식), 2n + 2(오른쪽 자식)  //  (n = 부모 노드의 인덱스 번호)

- 부모 노드 인덱스 =  Math.floor((n - 1) / 2)  //  (n = 자식 노드의 인덱스 번호)

 위의 수학 공식을 이용하여 배열에 데이터를 정렬하고 이를 통해 이진 힙 자료 구조를 구현할 수 있다.

 

18.3 이진 힙 클래스 

  이진 힙을 구현하는 초기 설정이 이진 탐색 트리와는 다르다. 이진 힙 에서는 노드 인스턴스를 따로 생성할 필요가 없다. 이진 힙 구현 자체를 배열을 통해서 하기 때문이다. 즉 필요한 것은 비어 있는 배열 하나로 초기 설정을 마친다. 그렇기 때문에 애초에 왼쪽부터 자식 노드가 채워지는 것이다. 결국 빈 배열에 이진 힙 구조에 맞게 배열을 구성하는 것이 핵심이다.

// 최대 이진 힙을 기준으로 코드를 구현
class MaxBinaryHeap {
    constructor(){
        this.values = [];
    }
}

18.4 Insert 메서드

  insert 메서드는 이진 힙 자료 구조에 값을 추가하는 것이다. 즉, 배열에 요소를 추가하고 이를 이진 힙 구조에 맞게 정해진 위치로 정렬시키는 것이다. 정렬을 하는 방법은 우선 추가 하고자 하는 요소를 배열의 맨 뒤에 push()를 활용해서 추가하고 새롭게 추가 된 노드가 현재 설정되어 있는 부모 노드보다 값이 크다면 부모 노드와 새롭게 추가된 노드의 자리를 바꿔준다. 이를 반복하여 정렬을 시켜준다. 이게 가능한 이유는 루트 노드는 항상 이진 힙 자료 구조 내에서 가장 큰 값을 가지기 때문이다.(자식들간의 순서는 중요하지 않고 부모 노드는 항상 자식 노드보다 커야한다는 규칙만 지켜지면 된다.) 이를 보통 '버블 업' 이라고 한다.

 

◎수도 코드

1) insert 이름의 메서드를 작성하고 숫자 하나를 인수로 받는다.

2) 포인터 역할을 할 인덱스 변수를 하나 만들고 새롭게 추가할 노드의 인덱스 번호를 할당한다. 

3) 일단 마지막 인덱스 자리, 즉 배열의 맨뒤, 맨 마지막에 새롭게 추가할 노드를 추가한다.

4) 그 후 부모의 인덱스를 찾는다.(수학 공식을 이용)

5) 그리고 어느 것이 더 큰지 비교 후, 추가하고자 하는 값이 더 크다면 두 값의 자리를 바꿔준다.

6) 그렇지 않다면 옳바른 자리에 위치한 것이기 때문에 그대로 멈추면 된다.

7) 반대로 자리를 바꾸게 된다면 포인터 역할을 하는 인덱스 변수에 바뀐 자리의 인덱스 번호, 즉 바뀌기 전에 있던 부모 노드의 인덱스 번호를 재할당해 준다.

8) 가장 앞 자리 즉, 루트 노드 자리로 오게 되면 더 이상 비교하지 않도록 코드를 추가해 줘야 에러가 발생하지 않는다.

 

// 최대 이진 힙을 기준으로 코드를 구현
class MaxBinaryHeap {
    constructor(){
        this.values = [];
    }
    
    insert(element){
        this.values.push(element);
        this.bubbleUp();
    }
    
    bubbleUp(){
        let idx = this.values.length - 1;
        const element = this.values[idx];
        while(idx > 0){
            let parentIdx = Math.floor((idx - 1)/2); 
            let parent = this.values[parentIdx];
            if(element <= parent) break;
            this.values[parentIdx] = element;
            this.values[idx] = parent;
            idx = parentIdx;
        }
    }
}

18.5 ExtractMax 메서드

  ExtractMax는 최대 이진 힙에서 루트 노드를 제거하는 기능을 하는 메서드다. 즉, 최대 이진 힙에서는 결국 최댓값인 루트를 제거하는 방법이고, 최소 이진 힙에서는 결국 최솟값인 루트를 제거하는 방법이다. 그리고는 루트에 알맞은 값이 올 수 있도록 해주어야 한다. 보통 이를 '싱크 다운', '버블 다운'이라고 표현한다. 전체적인 방법은 우선 가장 먼저 루트 노드와 배열의 마지막에 위치한 노드의 위치를 스왑해주고, pop() 메서드를 활용하여 기존 루트 노드를 제거해 준다. 그럼 배열의 맨 뒤의 노드는 루트 노드가 된다. 그 후 루트의 자식들 중(왼쪽/오른쪽) 더 큰 값과 비교하여 루트 노드의 값이 더 작다면 스왑해준다. 이를 반복하여 제 자리를 찾아가는 방식으로 구현한다.

 

◎수도 코드

1) 최대 이진 힙 클래스에 메서드를 작성하고 인수는 받지 않는다.

2) 우선 루트와 힙의 가장 끝 요소와 스왑하고 제일 뒤로 간 값을 제거한다(pop())

3) 새로운 루트 노드는 당연히 0번 인덱스에 위치하고, 자식 노드들과 비교해 나가면서 가라앉게 된다.

4) 인덱스 카운터라는 변수를 만들고 0에서 시작한다. 그리고 해당 인덱스 요소의 왼쪽 오른쪽 자식을 찾는다(수학 공식 이용)

5) 그 다음 두 자식들 중 더 큰 요소를 부모 위치의 요소와 비교한다.

6) 자식이 더 크다면 부모와 자식의 위치를 바꾼다.

7) 자리를 바꾼 자식의 인덱스를 새로운 부모 인덱스로 설정해 주고, 새로운 자식을 찾으면서 이 과정을 반복하여 루프를 돌고 자리를 바꾸는 것이다. 

8) 이 과정을 두 자식이 해당 요소보다 더 크지 않을 때까지 반복한다.

9) 그리고 마지막에 예전 루트를 출력해 준다.

class MaxBinaryHeap {
    constructor(){
        this.values = [];
    }
    insert(element){
        this.values.push(element);
        this.bubbleUp();
    }
    bubbleUp(){
        let idx = this.values.length - 1;
        const element = this.values[idx];
        while(idx > 0){
            let parentIdx = Math.floor((idx - 1)/2);
            let parent = this.values[parentIdx];
            if(element <= parent) break;
            this.values[parentIdx] = element;
            this.values[idx] = parent;
            idx = parentIdx;
        }
    }

    extractMax(){
        this.max = this.values[0];
        this.end = this.values.pop() // 제거된 요소가 반환됨
        if(this.values.length > 0){
            this.values[0] = end; // 배열에 요소가 하나가 남았을때를 방지! 이게 없으면 계속 하나가 남아 있음
            this.sinkDown();
        }
        return max;
    }
    sinkDown(){
        let idx = 0;
        const length = this.values.length;
        const element = this.values[0];
        while(true){
            let leftChildIdx = 2 * idx + 1;
            let rightChildIdx = 2 * idx + 2;
            let leftChild;
            let rightChild;
            let swap = null;

            if(leftChildIdx < length){
                leftChild = this.values[leftChildIdx];
                if(leftChild > element){
                    swap = leftChildIdx; // 어디로 자리를 바꿨는지 추적하는하기 위해 할당
                }
            }
            if(rightChildIdx < length){
                rightChild = this.values[rightChildIdx];
                if(
                    (swap === null && rightChild > element) || 
                    (swap !== null && rightChild > leftChild)
                    ) {
                        swap = rightChildIdx;
                    }
            }
            if(swap === null) break;
            this.values[idx] = this.values[swap]; //자리 바꾸기
            this.values[swap] = element; // 자리 바꾸기
            idx = swap; // 그 다음 자식들을 찾기 위해서 인덱스도 바꿔줘야함

        }
    }

}

18.6 우선 순위 큐

  여태까지 이진 힙에 대해서 공부하였는데 이진 힙을 배우는 이유 중 하나는 바로 우선 순위 큐를 만들기 위함이다. 우선 큐는 선입선출 구조의 자료 구조라고 앞서 공부했는데 우선 순위 큐는 각 요소가 그에 해당하는 우선순위를 가지는 데이터 구조를 말한다. 그리고 더 높은 우선 순위를 가진 요소가 더 낮은 우선 순위를 가진 요소보다 먼저 처리가 된다. 즉 데이터 모임이 있고 각 노드나 요소가 각각의 우선 순위 값을 가지고 있는 것이다. 우선 순위 큐는 서로 다른 우선 순위를 가지는 데이터나 정보를 관리할 필요가 있는 경우에 활용된다.

 

  하나 주의해야 할 점은 우선순위 큐가 힙과는 별개의 개념이라는 것이다. 우선 순위 큐는 추상적인 개념에 불과하다. 우선 순위 큐는 배열이나 연결 리스트를 가지고도 만들 수 있다. 즉 우선 순위 큐도 여러가지 방법에 의해 우선 순위를 가지는 데이터 구조만 갖춘다면 우선 순위 큐가 되는 것이다. 그래서 이진 힙을 사용해서 우선순위 큐를 구현하는 것도 하나의 방법일 뿐이다. 이진 힙에서 루트를 제거하는 성질을 해용해서 구현해 보는 것이다. 루트가 제거되면 버블 다운이 되면서 또 새로운 루트가 결정되는 것을 이용할 뿐이다. 

 

18.7 우선 순위 큐 & 노드 클래스

  우선 순위 큐 자체는 이진 힙과 같이 배열로 초기 설정이 되지만, 이진 힙과 다르게 우선 순위 큐는 노드 객체로 구성된다. 그리고 각 노드들은 value와 priority(우선 순위)를 프로퍼티로 갖는다.

class PriorityQueue{
    constructor(){
        this.values = [];
    }
}
//여기까지는 이진 힙과 동일함
// 다른 부분은 우선순위 큐는 노드를 가진다

class Node{
    constructor(val, priority){
        this.val = val;
        this.priority = priority;
    }
}

  주의 해야할 점은 노드의 값은 우선 순위 큐에 영향이 없다. 우선 순위 비교는 오로지 priority의 값 만을 사용한다. 즉, priority의 값이 실제로 힙을 구성하고 재정렬하는데 사용할 값이다. 최대 이진 힙의 경우 priority의 값이 클수록 우선 순위가 올라가는 것이고 최소 이진 힙의 경우에는 priority의 값이 작을수록 우선 순위가 올라가는 것이다. 다시 한 번 말하지만, 가장 중요한 것은 priority의 값을 가지고 이진 힙을 만드는 것이다.(value값을 비교하면 안된다.) 그것을 제외하고는 이진 힙을 구현하는 것과 거의 동일하다. 사실 이진 힙을 이용해서 우선 순위 큐를 구현하는 것이기 때문이다.

 

// 최소 이진 힙을 통한 우선 순위 큐 구현
class PriorityQueue {
    constructor(){
        this.values = [];
    }
    enqueue(val, priority){
        let newNode = new Node(val, priority);
        this.values.push(newNode);
        this.bubbleUp();
    }
    bubbleUp(){
        let idx = this.values.length - 1;
        const element = this.values[idx];
        while(idx > 0){
            let parentIdx = Math.floor((idx - 1)/2);
            let parent = this.values[parentIdx];
            if(element.priority >= parent.priority) break;
            this.values[parentIdx] = element;
            this.values[idx] = parent;
            idx = parentIdx;
        }
    }
    dequeue(){
        const min = this.values[0];
        const end = this.values.pop();
        if(this.values.length > 0){
            this.values[0] = end;
            this.sinkDown();
        }
        return min;
    }
    sinkDown(){
        let idx = 0;
        const length = this.values.length;
        const element = this.values[0];
        while(true){
            let leftChildIdx = 2 * idx + 1;
            let rightChildIdx = 2 * idx + 2;
            let leftChild,rightChild;
            let swap = null;

            if(leftChildIdx < length){
                leftChild = this.values[leftChildIdx];
                if(leftChild.priority < element.priority) {
                    swap = leftChildIdx;
                }
            }
            if(rightChildIdx < length){
                rightChild = this.values[rightChildIdx];
                if(
                    (swap === null && rightChild.priority < element.priority) || 
                    (swap !== null && rightChild.priority < leftChild.priority)
                ) {
                   swap = rightChildIdx;
                }
            }
            if(swap === null) break;
            this.values[idx] = this.values[swap];
            this.values[swap] = element;
            idx = swap;
        }
    }
}

class Node {
    constructor(val, priority){
        this.val = val;
        this.priority = priority;
    }
}

18.8 이진 힙 빅오 표기법

- Insertion : O(logN)

- Removal : O(logN)

- Search : O(N)

이진 힙은 최대 힙이든 최소 힙이든 삽입과 삭제에 있어서 아주 성능이 좋다.