[자료구조] 힙(Heap)

zzzzsb·2022년 7월 20일
0

힙(Heap)

힙은 완전 이진트리 기반의 자료구조로, 우선순위 큐를 구현하는데 사용된다.
트리 구조이기 때문에 삽입과 삭제에 O(logN)의 시간이 소요된다.

힙의 종류

힙의 종류에는 최대힙, 최소힙이 있다.
힙을 통해 최댓값이나 최솟값을 찾는 연산을 빠르게 수행할 수 있다.

최대 힙(Max-Heap)

트리의 root 노드에 가장 큰 값이 위치해 있다.
부모노드가 자식노드 보다 항상 크거나 같은 값을 가진다.

최소 힙(Min-Heap)

트리의 root 노드에 가장 작은 값이 위치해 있다.
부모노드가 자신노드 보다 항상 작거나 같은 값을 가진다.

힙 구현 with Javascript

  • 자바스크립트 외의 다른 언어에서는 힙 구조 자체를 기본 라이브러리로 제공해주는 경우가 많다.
    - Java, C++의 경우 PriorityQueue를 라이브러리로 제공해준다...ㅎ
    • Python3의 경우 heapq, heapify 함수 등으로 힙 구조화가 가능하다
    • 물론, 코딩테스트 외의 경우라면 자바스크립트도 외부 라이브러리를 통해 힙을 사용할 수 있다.

아무튼, 자바스크립트에서는 힙을 기본 라이브러리로 제공하지 않기에, 직접 구현해서 사용해야한다!

  • 힙을 구현하는 표준적인 자료구조는 배열이다.
  • 구현을 쉽게 하기 위해(계산의 편의성) 배열의 첫번째 인덱스인 0은 사용하지 않는다.
  • 힙은 완전 이진트리 기반의 자료구조이지만, 보통의 완전 이진트리와 다르게 반정렬 상태(느슨한 정렬 상태)를 유지한다.
    - 최대 힙이라면 큰 값이 부모노드에, 최소 힙이라면 작은 값이 부모노드에 배치되는 것만 유지
    • 왼쪽-오른쪽 자식노드는 부모 노드보다 작은 값을 유지하기만 하면 됨

힙에서 부모 노드 - 자식 노드의 관계

  • 왼쪽 자식 index = (부모 index) * 2
  • 오른쪽 자식 index = (부모 index) * 2 + 1
  • 부모 index = Math.floor(자식 index) / 2

전체 코드 - 삽입&삭제

class MinHeap {
    constructor() {
        this.heap = [ null ];
    }
    
    size() {
        return this.heap.length - 1;
    }
    
    getMin() {
        return this.heap[1] ? this.heap[1] : null;
    }
    
    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;
        }
    }
    
    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;
    }
}

힙의 응용

  • 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산
  • 우선순위 큐의 구현
    - 우선순위 큐는 배열, 연결리스트, 힙으로 구현할 수 있다
    • 그 중 힙으로 구현하는 것이 가장 효율적이다.
  • 다익스트라 알고리즘
  • 힙 정렬

참고 자료

profile
성장하는 developer

0개의 댓글