[자바스크립트 자료구조] 힙(Heap) - 힙 정렬 / 힙 시간복잡도

힙 정렬

• 지난 시간 까지 힙 클래스를 생성했으니 힙을 사용해서 정렬을 하는 것은 간단함
• 정렬된 배열을 얻기 위해 힙이 빈 상태가 될 때까지 힙에 대해 .pop()을 호출하면서 꺼낸 객체를 저장하기만 하면 된다.
• 삼투(bubbleUp, bubbleDown)가 O(logN)가 걸리고 정렬이 n개의 항목들을 꺼내야 하기 때문에 힙 정렬의 시간 복잡도는 O(NlogN)이다.
• 최소 힙을 이용하면 오름차순 정렬이 가능할 것이고, 최대 힙을 이용하면 내림차순 정렬이 가능할 것이다.

두가지 모두 sort()라는 메소드를 추가하면 된다. (MinHeap 클래스에 추가하면 MaxHeap은 상속받을 것이다)

sort(){

        let sort = [];

        const count = this.items.length;

        for(let i = 0; i < count; i++){

            sort.push(this.poll());

        }

        return sort;

    }

요약

🎁 힙은 배열을 사용해 표현한 트리와 같은 자료 구조

• 최솟값, 최댓값을 빨리 찾아내고 이를 이용해 정렬을 하기 쉬움

 

🎁 힙 노드 인덱스

노드	인덱스
자기 자신	N
부모	(N-1) / 2 이 때 소수점은 버리므로 사실상 자바스크립트에서는 Math.floor((N-1) / 2) 사용
왼쪽 자식	(N*2) + 1
오른쪽 자식	(N*2) + 2

 

 

🎁 힙은 삼투를 통해 자신의 구조를 유지

• bubbleUp : 노드가 삽입됐을 때 힙의 구조가 올바르게 될 때까지 항목들을 반복적으로 교환하면서 노드를 위로 이동시킴
• bubbleDown : 노드를 삭제할 때 루트 노드를 삭제하고 맨 마지막에 삽입했던 노드를 위로 올린 후 힙의 구조가 올바르게 될 때까지 항목들을 반복적으로 교환하면서 노드가 아래로 내려감

 

🎁 힙 연산 시간 복잡도

연산	시간 복잡도
삭제(아래로 이동)	O(logN)
삽입(위로 이동)	O(logN)
힙 정렬	O(NlogN)

 

전체 코드

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;
    }
}

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해둔 값 반환
    }
    sort(){
        let sort = [];
        const count = this.items.length;
        for(let i = 0; i < count; i++){
            sort.push(this.poll());
        }
        return sort;
    }
}

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.items); //array(5) [1, 8, 5, 100, 10]
console.log(minheap.sort()); 

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

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