[알고리즘👽] 18. 이진 힙

알고리즘

[알고리즘👽] 18. 이진 힙

머털박사 2022. 9. 21. 17:49

힙 (Heaps) 소개

힙은 트리의 일종입니다. 이 영상과 단원에서는 힙에 대해 배울 겁니다. 그렇지만 기본적으로 힙은 트리입니다. 힙도 종류가 많습니다. 우리가 집중해서 다룰 것은 이진 힙입니다.

목표

힙의 정의
최소 힙과 최대 힙 비교
둘 중 하나를 코딩해본다.
실생활에서 힙이 사용되는 예시와 힙을 사용해서 만들 수 있는 여러 데이터 구조 다루기

이진 힙이란 무엇인가?

이진 탐색트리와 매우 비슷하지만, 다른 규칙을 가지고 있다. 최대 이진 힙에서는 부모 노드가 항상 자식 노드보다 큰 값을 가진다. 최소 이진 힙에서는 부모 노드가 항상 자식보다 작은 값을 가진다.

최대 이진 힙

각각의 부모는 최대 두 개의 자식을 가진다.
최대 이진 힙에서는 부모 노드의 값이 언제나 더 큽니다.
최대 이진 힙에서는 부모가 언제나 자식보다 큽니다, 그렇지만 형제 노드 사이에는 그런 내용이 보장되지 않습니다.
이진 힙은 언제나 최적의 용량을 가진다. 다음 레벨로 내려가기 전에 모든 left와 right가 다 채워진다. 그리고 왼쪽이 먼저 채워진다.

이걸 왜 알아야하나요?

힙을 이용해서 우선순위 큐라는 것을 코딩하는 법을 배울 것이다. 아주 흔히 사용되는 것인데, 특히 그래프 순회라는 것에 자주 쓰인다.

힙 (Heaps) 정렬

트리나 노드 클래스를 만들어서 제작할 수 있다. 아니면 내장 데이터 구조인 배열, 또는 리스트를 사용해서 더 쉽게할 수 있다.

배열 안에 있는 모든 인덱스에 대해, 그 왼쪽 자식은 2n+1에 저장되어 있고 오른쪽 자식은 2n+2에 저장되어 있다.

즉 자식 노드의 인덱스가 n이면 부모의 인덱스는 (n-1)/2이다

힙 : Insert 메소드

최대 이진 힙에 무언가 삽입하는 경우는 이진 탐색 트리보다 복잡하다.

일단 왼쪽부터 채워나간다. 가장 뒤에 추가하려면 버블 업이라는 것을 해야한다. 만약 자식의 노드가 부모보다 크다면 자신과 부모의 노드를 바꾼다. 그리고 다시 부모의 노드와 부모의 부모의 노드를 비교한다.

먼저 삽입하고 그 다음 버블업 해주는 것이다.

의사코드

힙 안에 값을 배열 맨 뒤에 추가한다.
맞는 위치에 갈때까지 값을 버블업해준다.
- 값을 추가하고 해당 값의 부모인덱스를 찾는다 (index -1) / 2
- 해당 인덱스의 값과 배열 맨 뒤에 추가한 값을 비교한다.
- 추가한 값이 더 크다면 두 값의 자리를 바꿔준다. 그렇지 않다면 멈추면된다.

솔루션

class MaxBianryHeap {
    constructor(){
        this.values = [];
    }
    insert(element){
        this.values.push(element);
        this.bubbleUp();
    }
    bubbleUp(){
        let idx = this.values.length - 1;
        const element = this.values[idx];
        while(true){
            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;

        }
    }
}

힙 : ExtraMax 메소드

힙에서 무언가를 제거하는 방법

루트를 제거한다
가장 최근에 추가한 것과 대체한다
적용한다(sink down)
최대 힙에서 최대값을 그리고 최소 힙에서 최소값을 제거한 다음에 프로퍼티를 정리한다.

의사코드

가장 앞에 있는 요소를 제거하고 그 자리를 가장 뒤에 있는 요소로 대체한다.

솔루션

class MaxBianryHeap {
    constructor(){
        this.values = [];
    }
    insert(element){
        this.values.push(element);
        this.bubbleUp();
    }
    bubbleUp(){
        let idx = this.values.length - 1;
        const element = this.values[idx];
        while(true){
            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(){
        const max = this.values[0];
        const end = this.values.pop();
        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, rightChild;
            let swap = null;

            if(leftChildIdx < length) {
                leftChild = this.values[leftChildIdx];
                if(leftChild > element) {
                    swap = leftChildIdx;
                }
            }

            if(rightChildIdx < length) {
                rigthChild = 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;
        }
    }
}

우선순위 큐란?

각 요소가 그에 해당하는 우선순위를 가지는 데이터 구조. 데이터 모음이 있는데 각 노드, 또는 요소가 각각에 대한 우선순위 값을 가지고 있는 거다. 우선순위 큐와 힙은 별개이다. 이것들은 그저 추상적인 개념에 불과하다. 우선순위 큐는 배열이나 리스트를 가지고 만들 수도 있다. 좋은 방법이 아니고 느리긴 하지만 가능하다.

우선순위 큐(Queue) 의사코드

Class Name : PriorityQueue, Properties: values = []

Class Name: Node, Properties: val, priority

최소 이진 힙 - 작은 숫자가 높은 우선순위를 뜻한다.
각각 노드는 값과 우선순위를 가진다. 우선순위를 사용해서 힙을 구성한다.
Enqueue 메서드는 새로운 노드를 만들기 위해 값과 우선순위를 받아들인다. 그리고 우선순위에 기초해서 오른쪽에 둔다
Dequeue 메서드는 투트 요서를 제거하고 반환한다. 그리고 우선숭위를 사용해서 힙을 재배열한다.

우선순위 큐(Queue) 솔루션

class PriorityQueue{
    constructor(){
        this.values = [];
    }
    enqueque(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(true){
            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();
        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) {
                rigthChild = 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;
    }
}

let ER = new PriorityQueue();
ER.enqueue("common cold", 5)
ER.enqueue("gunshot wound", 1)
ER.enqueue("high fever", 4)
ER.enqueue("broken arm", 2)
ER.enqueue("glass in foot", 3)

이진 힙의 빅오(BIG O)

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

메서드	빅오
Insertion	O(log N)
Removal	O(log N)
Search	O(N)

저작자표시

'알고리즘' 카테고리의 다른 글

[알고리즘👽] 20. 그래프 (1)	2022.09.23
[알고리즘👽] 19. 해시 테이블 (0)	2022.09.22
[알고리즘👽] 17. 트리 순회 (0)	2022.09.20
[알고리즘👽] 16. 이진 검색 트리 (0)	2022.09.20
[알고리즘👽] 15. 스택과 큐 (0)	2022.09.19

현재글[알고리즘👽] 18. 이진 힙

개발

프론트엔드 중심으로 공부한 내용 정리해서 업로드합니다.

알고리즘, 프론트엔드 면접질문, Tailwind단점, javascirpt, REACT, git 초기화, git push -u option, JavaScript, 회고록, OpenSlide, git push -u 옵션, git push -u origin main 뜻, gitlab github 차이, js유효성검사, git과 github차이, 알고리즘 큐, git init 초기화, Tailwind장점, 알고리즘 스택, http 캐시,

Today :
Yesterday :

개발