(JS 알고리즘) 이진 힙(Binary Heap)과 우선순위 큐(Priority Queue)

정태호·2023년 3월 24일
JavaScript알고리즘
0

Javascript 알고리즘 및 자료구조(Colt Steele 강의 참고)

목록 보기
8/13

이진 힙(Binary Heap)과 우선순위 큐(Priority Queue)

힙이란?

  • Heap의 사전적 의미는 무엇인가 차곡차곡 쌓여있는 더미를 의미한다. 이를 통해, 자료 구조에서 힙이란 모래 더미처럼 삼각형 구조로 쌓여있는 구조임을 추측할 수 있다.

    • 메모리 영역 Heap과 자료구조 Heap은 서로 상관관계가 없다. 메모리 영역 Stack은 자료구조 Stack를 사용하기에 Stack이라고 불리는 것과 달리, 메모리 영역 Heap은 자료구조 Heap을 사용하지 않는다. 단지, 영단어 힙(heap)은 '무엇인가 차곡차곡 쌓여있는 더미'라는 뜻을 지니고 있어, 사용 가능한 메모리 풀을 관용적으로 ‘Heap’이라고 불렀다고 한다.

  • 힙(Heap)도 트리 자료 구조의 일종이다. 힙이 다른 트리와는 달리 데이터가 한 쪽으로 쏠리지 않고 모래 더미처럼 삼각형의 형태를 유지할 수 있는 이유는, 부모 노드가 항상 자식 노드들보다 크거나(최대이진힙) 작아야(최소이진힙) 한다는 규칙이 있고 형제 노드들 간의 관계에는 그러한 규칙이 없기 때문이다.

이진 힙(Heap)

  • 최대 이진힙(MaxBinaryHeap)에서는 부모 노드가 항상 자식 노드보다 커야한다.

  • 최소 이진힙(MinBinaryHeap)에서는 부모 노드가 항상 자식 노드보다 작아야한다.

  • 이진 힙에서 부모와 자식 노드 간의 관계는 위와 같이 크거나 작아야 하지만, 형제 노드들 간의 관계에는 그러한 규칙이 없다.

  • 이진 힙은 언제가 가능한 가장 적은 최적의 공간만을 차지한다.

  • 이진 힙은 자료구조에서 자주 사용되는 우선순위 큐(Priority Queue)나 그래프 순회 알고리즘 등에서 자주 사용된다

부모와 자식 - 서로의 값을 찾는 규칙

  • 이진 힙과 이진탐색트리의 차이점을 이해하자. 둘은 비슷해보이지만 다르다.
  • 어떤 요소(인덱스 n)에 대한 child들의 인덱스는 각각 다음과 같다는 규칙이 있다. 예를 들어, 인덱스 2(val = 8)에 대한 left child의 인덱스는 5(2(n=2)+1)이며, right child의 인덱스는 6(2(n=2)+2)이다.
  • 부모의 위치(n)를 가지고 자식의 위치 찾기
    • left child 인덱스 : 2n+1
    • right child 인덱스 : 2n+2
  • 반대로 child 노드의 인덱스를 가지고 parent 노드의 인덱스를 찾을 수도 있다.
  • 자식의 위치(n)를 가지고 부모의 위치 찾기
    • parent 인덱스 : Math.floor((n-1)/2)

최대 이진 힙 기본 구조

class MaxBinaryHeap {
  constructor() {
    this.values = [];
  }
}

이진 힙 Insert 메소드

  • 로직
    1. 제일 밑에 요소를 넣는다. this.values.push(element);
    2. 그 요소가 알아서 제 자리로 가도록 비눗방울처럼 띄어 올린다. this.bubbleUp();

  • 아래 이미지는 [41,39,33,18,27,12] 이진 힙 데이터에 55를 Insert했을 때 발생하는 과정을 시각화한 것이다.

  • 코드

    insert(element){
      //삽입하려는 요소를 배열 끝에 push
        this.value.push(element);
      //BubbleUp()메소드를 호출하여 올바른 위치로 정렬할 예정
        this.BubbleUp();
    }

    BubbleUp(){
        var idx = this.value.length - 1; //들어온 값의 인덱스
        const element = this.value[idx] //들어온 값
		//인덱스가 0이 되면 그것이 루트라 더이상 비교할 것이 없다.
        while(idx > 0){
          	//자식 인덱스를 사용하여 부모인덱스 찾기
            var parentIdx = ~~((idx-1)/2);
          	//변수에 부모 값 저장
            var parent = this.value[parentIdx];
			// 부모보다 작으면 루프 종료	
            if(element <= parent) break;
          	// 부모보다 크면 스왑해준 뒤 그 요소를 다시 자식으로 해서 다시 루프 반복
            this.value[parentIdx] = element;
            this.value[idx] = parent;
            idx = parentIdx;
        }
    }

이진 힙 ExtractMax 메소드

  • 최대이진힙에서 root(가장 큰 값)를 제거하는 메서드다. 이진힙을 기반으로 한 우선순위 큐에서 최우선순위를 가져오고 제거할 때 사용하는 알고리즘이다.

  • 메소드 로직
    1. root를 제거한다.
    2. root 자리에 가장 마지막 요소를 옮겨 넣는다.
    3. root 자리에 옮겨진 요소가 제자리를 찾아서 내려가도록 조절한다.

  • 아래 이미지는 [41,39,33,18,27,12] 이진 힙에서 ExtractMax()를 했을 때, 발생하는 과정을 시각화한 것이다.
    1. 먼저 41을 제거하고 이를 나중에 리턴한다.
    2. 가장 최근에 추가된(가장 뒤에 있는) 12를 root 자리로 옮겨 넣는다.
    3. root 자리에 올라선 12가 제자리로 돌아가기 위해서 child 값과 비교하고 child 값 중 더 큰 것과 자리를 바꾼다.
    4. 한 단계 아래로 내려간 12가 다시 그 아래 child 중 값이 큰 녀석인 27과 크기를 비교하고, 12가 더 작으므로 12와 27이 자리를 서로 바꾼다.
    5. 12 아래에 더 이상 하위 child가 없으므로 반복문 종료하고, 제거했던 41을 return한다.

  • 코드
extractMax(){
        var max = this.value[0]; //루트값이 가장 큰 값이다
        var end = this.value.pop();//배열 가장 마지막 요소
  		//pop()한 후 배열에 요소가 남아있으면
        if(this.value.length > 0){
          	//root에 가장 마지막 요소 end를 넣고
            this.value[0] = end;
          	//제자리를 찾아가도록 sinkDown() 호출
            this.sinkDown();
        }
  		//가장 큰 요소를 반환
        return max;
    }

    sinkDown(){
        var idx = 0;
        var element = this.value[idx];
        
        while(true){
          	//부모 인덱스로부터 자식 인덱스를 찾는 공식 이용
            let leftchildIdx = idx * 2 + 1;
            let rightchildIdx = idx * 2 + 2;
            var leftchild,rightchild;
            var swap = null;
            
          	//left 인덱스가 배열 길이보다 작으면
            if(leftchildIdx < this.value.length){
                leftchild = this.value[leftchildIdx];
                if(leftchild > element){
                    swap = leftchildIdx;
                }
            }
            //right 인덱스가 배열 길이보다 작으면
            if(rightchildIdx < this.value.length){
                rightchild = this.value[rightchildIdx];
              	//왼쪽에서 스왑이 발생하지 않을 수 있으므로 발생하지 않고
              	// 비교요소보다 right가 더 큰지 비교 or 왼쪽요소도 비교요소보다는 크지만 
              	//right 자식보다는 작으면 swap을 오른쪽 값으로 바꿈
                if((swap === null && element < rightchild) 
                || (swap !== null && leftchild < rightchild)){
                        swap = rightchildIdx;
                   }
            }
			
            if(swap === null) break;
          	//선정된 swap 인덱스로 요소들을 교환한 뒤 재할당 후 자식요소 찾기로 다시 반복
            this.value[idx] = this.value[swap];
            this.value[swap] = element;
            idx = swap;
        }   
    }

우선순위 큐(Priority Queue)

  • 우선순위 큐는 각각의 요소가 개별 우선순위를 갖는 자료구조다. 높은 우선순위를 가진 요소는 낮은 우선순위를 가진 요소보다 앞에 온다.
  • 우선순위 큐가 보통 힙(Heap)을 사용하기 때문에, 이 둘이 같거나 관계가 있다고 생각할 수도 있으나, 우선순위 큐와 힙(Heap)은 상관관계가 없다. 우선순위 큐는 단지 추상적인 개념에 불과하며, 힙 외에 배열이나 리스트 등의 다른 방식으로도 구현할 수 있다.
    • 하지만 힙(Heap)이 더 좋은 성능(삽입, 제거 모두 O(log n))을 갖기 때문에, 힙으로 큐를 구현해보자.

구현

  • 최소이진힙 으로 구현하고 value 외에도 priority(우선순위) 클래스를 함께 담기 위해 Node 클래스를 사용한다.
  • 로직은 이진 힙과 비슷하나 큐에 사용하는 메소드들로 이름을 변경하고 최대 이진 힙이 아니라 우선순위 비교에 따른 최소 이진 힙으로 구성했음을 주의하자!
class Node{
    constructor(val,priority){
        this.val = val;
        this.priority = priority; //우선순위가 추가됨
    }
}
class PriorityQueue{
    constructor(){
        this.val = [];
    }

    enqueue(val,priority){ //insert에서 큐에 쓰이는 enqueue로 변경
        let newNode = new Node(val,priority); //Node는 값과 우선순위를 가지고 있음
        this.val.push(newNode);
        this.BubbleUp();
    }

    BubbleUp(){
        var idx = this.val.length - 1;
        const element = this.val[idx];
        while(idx > 0){
            var parentIdx = Math.floor((idx-1)/2);
            var parent = this.val[parentIdx];
          	//값을 비교하는게 아니라 값이 가진 우선순위로 비교
          	//우선순위는 1,2,3,4 처럼 낮은 숫자가 가장 크다
            if(element.priority >= parent.priority) break;
            this.val[parentIdx] = element;
            this.val[idx] = parent;
            idx = parentIdx;
        }
    }

    dequeue(){ //extractMax(최댓값 반환)을 dequeue로 변경
        var min = this.val[0];
        const end = this.val.pop();
        if(this.val.length > 0){
            this.val[0] = end;
            this.Sinkdown();
        }
        return min;
    }

    Sinkdown(){
        var idx = 0;
        var element = this.val[idx];
        while(true){
            let leftchildIdx = idx * 2 + 1;
            let rightchildIdx = idx * 2 + 2;
            var leftchild,rightchild;
            var swap = null;
			//마찬가지로 로직은 비슷하나 값의 우선순위로 비교한다
            if(leftchildIdx < this.val.length){
                leftchild = this.val[leftchildIdx];
                if(leftchild.priority < element.priority){
                    swap = leftchildIdx;
                }
            }

            if(rightchildIdx < this.val.length){
                rightchild = this.val[rightchildIdx];
                if((rightchild.priority < element.priority && swap === null)||
                  (swap !== null && rightchild.priority < leftchild.priority)){
                    swap = rightchildIdx;
                  }
            }
            if(swap === null) break;
            this.val[idx] = this.val[swap];
            this.val[swap] = element;
            idx = swap;
        }
    }
}

이진 힙 성능

  • 시간복잡도
    • 삽입 : O(logN)
    • 제거 : O(logN)
    • 탐색 : O(N)
  • 이진 힙은 최대이진힙이든 최소이진힙이든 삽입과 삭제에 있어서 성능이 아주 좋다. 이진 힙 구조 특성상 데이터가 한 쪽으로 쏠리지 않으므로, 언제나 삽입과 제거에 있어서 평균적인 O(logN)의 시간복잡도를 갖는다.
    • 힙은 한줄이 다 채워지지 않아도 되는 BST와 달리 왼쪽 오른쪽을 다 채워야 다음으로 넘어갈 수 있다.
  • 이진 힙은 탐색에서는 시간복잡도가 좋은 편이 아니므로 탐색에 대한 최적화가 필요하다면 다른 자료구조를 고려하는 것이 낫다.
    • 이진 힙의 형제 노드 사이에 순서가 정해져 있지 않기 때문에, 무언가를 찾으려면 왼쪽과 오른쪽을 항상 모두 탐색해야 하기 때문에 탐색에서 O(N)의 시간복잡도를 가진다.
profile
정태호
주니어 프론트엔드 개발자가 되고 싶습니다!
이전 포스트

(JS 알고리즘) 트리 순회 - BFS(너비우선탐색), DFS(깊이우선탐색)

다음 포스트

(JS 자료구조) 해시 테이블(Hash Table) - 해시 맵

0개의 댓글