[자바스크립트 자료구조] 힙(Heap) - (1) 최소힙, 최대힙 구현

힙(Heap)

 

힙이란?

• 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조
• 힙에는 최소힙과 최대힙이 있음

최소힙

작은 값을 항상 트리의 위에 있게 해서 트리의 루트에는 가장 작은 값이 오도록 함

 

최대힙

가장 큰 값이 맨 위에 오도록 함. 모든 노드는 자기 부모 노드가 자기보다 큰 값을 가지고 있음

---

힙에 데이터를 삽입하고 값을 꺼내오는 방법

최소힙에 데이터를 삽입하는 방법

1. 저런 트리가 있다고 하자
2. 1을 삽입하려고 할 때 완전이진트리의 요건을 만족시키기위해 저 자리에 삽입
3. 자신의 값과 자신의 부모노드값을 비교하여 자신의 값이 더 작으면 자리를 바꿈
4. 3번의 과정을 자신의 값이 부모노드값보다 작을때까지 혹은 루트에 도착할 때까지 반복한다.

• 이 작업은 밸런스가 맞춰져있는 완전이진트리에서 이루어지니까 한 레벨씩 루트까지 올라간다면 한번 돌때마다 절반씩 뚝뚝 떨어지니까 O(log(n))의 시간복잡도를 가진다.

 

최소힙에서 최솟값 꺼내오기

1. 이런 최소힙이 있을 때, 최솟값은 당연히 루트에 있으므로 1을 가져온다.

2. 루트 자리가 비어버렸으니 채워야 한다. 완전 이진 트리의 맨 마지막 노드를 가져온다.

3. 가져오니까 정렬이 안되어 있는 상태이므로 자신의 자식 노드와 비교해서 자기보다 작은 노드와 자리를 바꾼다.

4. 내려와서 자기보다 작은 자식 5랑 또 자리를 바꾼다

5. 이렇게 반복하다가 자식이 자기보다 크거나 리프노드에 도달하게 되면 멈춘다

* 이 작업은 루트에서 한 레벨씩 내려가다가 맨 마지막 레벨까지 내려갈 수 있으니 최대 O(log(n))의 시간이 걸린다. 한 번 돌아갈 때마다 가야할 길이 절반으로 뚝뚝 떨어지기 때문에

 

 

🌻bubbleUp

힙에 값을 삽입할 때 부모와 비교해서 값이 크거나 작으면(최소 힙의 경우 부모가 자신보다 크면, 최대 힙의 경우 부모가 자신보다 작으면) 부모와 값을 교환해서 올바르게 정렬이 될 때 까지 올라가는 것을 편의상 bubbleUp이라 하고

 

🌼bubbleDown

힙에서 값을 꺼내올 때 아래 자식들과 비교해서 값이 크거나 작으면(최소 힙의 경우 자식이 자신보다 값이 작으면, 최대 힙의 경우 자식이 자신보다 값이 크면) 자식과 값을 교환해서 올바르게 정렬이 될 때 까지 내려가는 것을 편의상 bubbleDown이라고 하겠다.

 

★ 최대힙은 최소힙과 이처럼 값의 비교 연산자만 다르고 나머지는 똑같기 때문에 최대힙은 생략하겠다.

---

힙은 배열로 구현

- 다른 자료 구조와 달리 힙은 자식에 대한 포인터를 갖는 대신에 배열을 사용해서 자료를 저장함

- 배열의 인덱스는 각 항목의 차수/높이를 정의

- 첫 번째 배열 항목을 루트로 설정한 다음 각 왼쪽 항목과 오른쪽 항목을 순서대로 채움으로써 이진 힙을 다룰 수 있음

- 다음 그림 속 힙의 경우 배열은 [2,4,23,12,13]이 된다.

 

이진 힙 배열 인덱스 구조

• 이진 힙의 경우 힙을 나타내기 위해 배열이 사용되는데 다음과 같이 인덱스를 사용한다. 이 때 N은 노드의 인덱스이다.
  • 자신 : N
  • 부모 :  (N-1) / 2
  • 왼쪽 자식 : (N*2) + 1
  • 오른쪽 자식 : (N*2) + 2
• 예를 들어서 3번을 예로 들면 - 자신은 3   /  부모는 (3-1)/2 = 1 / 왼쪽 자식은 (3*2) + 1 = 7 /  오른쪽 자식은 (3*2) + 2 = 8 ,
• 4번을 예를 들면 자신은 4, 부모는 (4-1) /2 = 1.5 인데 소수점 버리고 1, 왼쪽 자식은 (4*2) + 1 = 9 , 오른쪽 자식은 (4*2) + 2 = 10

 

---

힙/최소힙/최대힙 구현코드

 

기본 힙(Heap)

class Heap{

    constructor(){

        this.items = [];

    }



    //값을 서로 바꾸는 메소드

    swap(index1, index2){

        let temp = this.items[index1]; // items의 index1의 값을 temp(임시공간)에 담음

        this.items[index1] = this.items[index2]; // index1에 index2의 값을 저장

        this.items[index2] = temp; // index2에 아까 index1의 값을 temp에 넣어놓은 값을 저장

    }



    //부모 인덱스 구하는 메소드

    parentIndex(index){

        return Math.floor((index-1) / 2);

    }



    //왼쪽 자식 인덱스 구하는 메소드

    leftChildIndex(index){

        return index * 2 + 1;

    }



    //오른쪽 자식 인덱스 구하는 메소드

    rightChildIndex(index){

        return index * 2 + 2;

    }



    //부모 노드 구하는 메소드

    parent(index){

        return this.items[this.parentIndex(index)];

    }



    //왼쪽 자식 노드 구하는 메소드

    leftChild(index){

        return this.items[this.leftChildIndex(index)];

    }



    //오른쪽 자식 노드 구하는 메소드

    rightChild(index){

        return this.items[this.rightChildIndex(index)];

    }



    //최대 힙의 경우 최댓값을 반환하고 최소 힙의 경우 최솟값을 반환하는 메소드

    peek(){

        return this.items[0];

    }



    //힙의 크기(항목 개수)를 반환하는 메소드

    size(){

        return this.items.length;

    }

}

 

최소 힙(MinHeap)

Heap 클래스를 상속받았으므로 Heap 클래스 안에 있는 모든 함수를 사용할 수 있다

class MinHeap extends Heap{

    // MinHeap 클래스는 Heap 클래스를 상속받았으므로 Heap 클래스의 메소드를 모두 사용할 수 있다.



    bubbleUp(){

        let index = this.items.length-1;

        while(this.parent(index) !==undefined && this.parent(index) > this.items[index]){

            this.swap(index, this.parentIndex(index));

            index = this.parentIndex(index);

        }

    }



    bubbleDown(){

        let index = 0;



        while(this.leftChild(index) !==undefined && (this.leftChild(index) < this.items[index] || this.rightChild(index) < this.items[index]){

            let smallerIndex = this.leftChildIndex(index);

            if(this.rightChild(index) !==undefined && this.rightChild(index) < this.items[smallerIndex]){

                smallerIndex = this.rightChildIndex(index);

            }

            this.swap(index, smallerIndex);

            index = smallerIndex;

        }

    }



    // 힙에 원소를 추가하는 함수

    add(item){

        this.items[this.items.length] = item;

        this.bubbleUp();

    }



    // 힙에서 원소를 빼내는 함수

    // 최소 힙이라면 최솟값이 빠져나올 것이고 최대힙이라면 최댓값이 빠져나온다.

    poll(){

        let item = this.items[0]; // 첫번째 원소 keep

        this.items[0] = this.items[this.items.length - 1]; // 맨 마지막 원소를 첫번째 원소로 복사

        this.items.pop(); // 맨 마지막 원소 삭제

        this.bubbleDown();



        return item; // keep해둔 값 반환

    }

}

 

최대 힙(MaxHeap)

Heap 클래스를 상속받았으므로 Heap 클래스 안에 있는 모든 함수를 사용할 수 있다

class MaxHeap extends MinHeap{
    //MaxHeap의 경우 MinHeap을 상속받았으므로 MinHeap의 모든 함수를 사용할 수 있지만 bubbleUp과 bubbleDown은 Overriding(재정의)하였다.
    bubbleUp(){
        let index = this.items.length - 1;
        while(this.parent(index) !== undefined && this.parent(index) < this.items[index]){
            this.swap(index, this.parentIndex(index));
            index = this.parentIndex(index);
        }
    }

    bubbleDown(){
        let index = 0;
        
        while(this.leftChild(index)  !== undefined && (this.leftChild(index) > this.items[index] || this.rightChild(index) > this.items[index]){
            let largerIndex = this.leftChildIndex(index);
            if(this.rightChild(index)  !== undefined && this.rightChild(index) > this.items[largerIndex]){
                largerIndex = this.rightChildIndex(index);
            }
            this.swap(largerIndex, index);
            index = largerIndex;
        }
    }
}

 

사용하는 코드

//앞서 구현한 heap.js를 사용하는 코드!

//최소 힙을 사용하는 코드
const minheap = new MinHeap();
minheap.add(1);
minheap.add(10);
minheap.add(5);
minheap.add(100);
minheap.add(8);

console.log(minheap); //array(5) [1, 8, 5, 100, 10]
console.log(minheap.poll()); // 1
console.log(minheap.poll()); // 5
console.log(minheap.poll()); // 8
console.log(minheap.poll()); // 10
console.log(minheap.poll()); // 100
console.log(minheap); // array(0)


//최대 힙을 사용하는 코드
const maxheap = new MaxHeap();
maxheap.add(1);
maxheap.add(10);
maxheap.add(5);
maxheap.add(100);
maxheap.add(8);

console.log(maxheap); //array(5) [100, 10, 5, 1, 8]
console.log(maxheap.poll()); // 100
console.log(maxheap.poll()); // 10
console.log(maxheap.poll()); // 8
console.log(maxheap.poll()); // 5
console.log(maxheap.poll()); // 1
console.log(maxheap); // array(0)