23.07.11 자료구조 힙(heap) 코드 분석

 내가 지금 힙을 구현하려면 어떻게 해야하나 막막해서 다른 누군가가 구현한 힙 코드를 해석해봤다.

 

class MinHeap {
    constructor() {
        this.heap = [ null ];
    }

• 힙이 구현될 공간, 편의상 0번 인덱스는 비우고 1번부터 시작해서 순서 및 이후 인덱스 계산을 보기 편하게 해주었다.

 

 size() {
        return this.heap.length - 1;
    }

• 힙의 사이즈, 배열의 길이를 반환하면 되는데 0번은 비워둔 상태로 만들었기에 -1을 해준다.

 

 getMin() {
        return this.heap[1] ? this.heap[1] : null;
    }

•  힙 안에 가장 작은 값, 인덱스 0을 비워뒀기에 인덱스 1이 가장 작은 값이다.

 

swap(a, b) {
        [ this.heap[a], this.heap[b] ] = [ this.heap[b], this.heap[a] ];
    }

•  두 노드의 값을 바꾸는 메서드 이후에 사용 된다.

 

heappush(value) {
        this.heap.push(value);
        let curIdx = this.heap.length - 1;
        let parIdx = (curIdx / 2) >> 0;
        
        while(curIdx > 1 && this.heap[parIdx] > this.heap[curIdx]) {
            this.swap(parIdx, curIdx)
            curIdx = parIdx;
            parIdx = (curIdx / 2) >> 0;
        }
    }

•  힙에 새로운 요소 추가
  
  반복문 전
  1. 가장 마지막 인덱스에 추가한다.
  2. 추가한 데이터의 인덱스를 변수에 담는다.
  3. 부모 노드의 인덱스를 구한다.
  
  반복문
  1. 부모 노드가 존재해야하며(조건1) 부모 노드가 자식 노드보다 커야한다.(조건2)
  2. 조건을 만족하면 부모 노드와 자식 노드의 값을 바꾼다. this.heap[parIdx]과 this.heap[parIdx]의 값이 바뀐다.
  3. 현재 노드의 인덱스를 부모 노드의 인덱스와 바꾼다. ->  2에서 값이 바뀌었기에 인덱스도 바꿔준다.
  4. 다시 부모 노드의 인덱스를 찾아 위 과정 반복
  
  기존 값보다 작은 값이 추가 된다면 이렇게 반복을 통해 위치를 찾아간다.

 

heappop() {
        const min = this.heap[1];	
        if(this.heap.length <= 2) this.heap = [ null ];
        else this.heap[1] = this.heap.pop();   
        
        let curIdx = 1;
        let leftIdx = curIdx * 2;
        let rightIdx = curIdx * 2 + 1; 
        
        if(!this.heap[leftIdx]) return min;
        if(!this.heap[rightIdx]) {
            if(this.heap[leftIdx] < this.heap[curIdx]) {
                this.swap(leftIdx, curIdx);
            }
            return min;
        }

        while(this.heap[leftIdx] < this.heap[curIdx] || this.heap[rightIdx] < this.heap[curIdx]) {
            const minIdx = this.heap[leftIdx] > this.heap[rightIdx] ? rightIdx : leftIdx;
            this.swap(minIdx, curIdx);
            curIdx = minIdx;
            leftIdx = curIdx * 2;
            rightIdx = curIdx * 2 + 1;
        }

        return min;
    }

•  힙에서 요소 삭제 ( 가장 작은 값이 나온다 )
  
  반복문 전
  1. 인덱스 1번이 가장 작은 값
  2.  0번 인덱스는 일부러 비워둔 값이기에 길이가 2 이하면 가장 작은 값을 꺼낸 힙은 null만 남는다.
  3.  그 외에 경우엔 가장 마지막 값이 루트 노드 자리를 채운다.
  4.  루트 노드 자리에 둔 값의 인덱스를 변수에 담는다. 
  5.  루트 노드의 인덱스가 부모 노드가 되어 자식 노드1(왼쪽), 자식 노드2(오른쪽)의 인덱스를 구한다.
  6.  자식 노드1이 없다면 바로 가장 작은 값만 리턴
  7.  자식 노드1은 있는데 자식 노드2가 없다면 임시 노드와 자식 노드1만 비교해서 자리를 조정 후 가장 작은 값만 리턴
  
  반복문
  1. 자식 노드1 혹은 자식 노드2가 부모 노드보다 작아야 한다. 
  2.  자식노드1, 자식노드2 중에 누가 더 작냐를 삼항 연산자로 구한다.
  3.  2에서 찾은 값을  부모 노드 자리에 둔다. 
  4.  값을 조정 했으니 인덱스도 자식 노드의 인덱스로 바꾼다.
  5.  자식 노드의 자식 노드1,2를 구한다
  6. 기존 자식 노드는 부모 노드가 되고 자식 노드의 자식 노드들이 각각 자식노드1,2가 되어 다시 위 과정 반복
  
  이렇게 루트 노드가 빠진 자리를 다시 재조정 한다.

 

이렇게 힙이 어떻게 구현되는지 해석해 봤다. 힙을 직접 구현하진 못하더라도 코드를 뜯어보니 어떻게 작동 되는지 더 명확하게 알게 되었고 나중에 필요에 하다면 참고하여 사용할 수 있을 것 같다.

 

이거 그냥 sort()로 정렬하면 되는 거 아닌가 생각도 들었지만 sort()는 새로운 값을 추가하거나 삭제할 때 전체 데이터를 확인하고 움직여야 하는데 힙은 경우에 따라 차이는 있겠지만 일부만 뒤져도 우선 순위에 맞게 정렬을 할 수 있다는 점에서 더 유용하고 빠르다

 

참고