[6][알고리즘 - 정렬] 힙정렬(Heap Sort)이란? javascript 구현

힙 정렬이란?

 

주어진 데이터들을 이진 트리로 

구성하여 정렬하는 방법

입니다.

 

조금더 디테일 하게는

내림차순 정렬을 위해서는 최대 힙 트리를 구성하고

오름차순 정렬을 위해서는 최소 힙 트리를 구성하여

정렬을 하는 방법입니다.

 

출처 - https://commons.wikimedia.org/wiki/File:Heap_sort_example.gif

 

 

그러고 보니 힙(heap)이라는 것이 무엇일까요?

 

힙(heap)이란?

 

힙은 최댓값 및 최솟값을 찾아내는

연산을 빠르게 하기 위해 고안된

완전이진트리를 기본으로 한 자료구조

입니다.

 

힙에서 두가지 최대힙과 최소힙으로 나눠집니다.

 

따라서,

최대힙(Max Heap)은

큰 값이 위로 오도록,

최소힙(Min Heap)은

작은 값이 위로 오도록

구성하는 트리구조 입니다.

 

이처럼,

root에 가장 큰 값 또는 가장 작은 값을 올리고

최종적으로 해당 값을 마지막 위치로 교환하여

정렬을 하는 방식입니다.

 

그럼, 최대값 또는 최소값 힙을 구성하여

오름차순, 내림차순으로

javascript 로 구현해 보겠습니다.

 

class Heap {
    #heap;
    #type = 'min'; // 최대, 최소 구분
    constructor(type) {
        this.#heap = [];
        this.#type = type;
    }

    // 부모 정점
    parentIndex = (index) => Math.floor((index - 1) / 2);
    // 왼쪽 자식
    leftChildIndex = (index) => (2 * index + 1);
    // 오른쪽 자식
    rightChildIndex = (index) => (2 * index + 2);

    // 위치 변경
    swap = (a, b) => {
        let temp = this.#heap[a];
        this.#heap[a] = this.#heap[b];
        this.#heap[b] = temp;
    }

    // 힙구조로 만들기
    insert = (arr) => {
        for (let i = 0; i < arr.length; i++) {
            this.#heap.push(arr[i]);
            var index = this.#heap.length - 1;
            var parent = this.parentIndex(index);

            // 최대힙 > 큰 값이 root
            if (this.#type === 'max') {
                while (this.#heap[parent] < this.#heap[index]) {
                    this.swap(parent, index);
                    index = this.parentIndex(index);
                    parent = this.parentIndex(index);
                }
            }
            // 최소힙 > 작은 값이 root 또는 기본값
            else {
                while (this.#heap[parent] > this.#heap[index]) {
                    this.swap(parent, index);
                    index = this.parentIndex(index);
                    parent = this.parentIndex(index);
                }

            }


        }
    }

    delete = () => {
        // 가장 마지막 값을 처음으로 이동
        var item = this.#heap.shift();
        this.#heap.unshift(this.#heap.pop());

        // 다시 힙 구조로 만들기 Start
        var index = 0;
        var leftChild = this.leftChildIndex(index);
        var rightChild = this.rightChildIndex(index);

        // 최대힙 > 큰 값이 root
        if (this.#type === 'max') {
            while (this.#heap[leftChild] > this.#heap[index] || this.#heap[rightChild] > this.#heap[index]) {
                var min = leftChild;
                if (this.#heap[rightChild] > this.#heap[min]) {
                    min = rightChild
                }
                this.swap(min, index);
                index = min;
                leftChild = this.leftChildIndex(min);
                rightChild = this.rightChildIndex(min);
            }
        }
        // 최소힙 > 작은 값이 root
        else {
            while (this.#heap[leftChild] < this.#heap[index] || this.#heap[rightChild] < this.#heap[index]) {
                var min = leftChild;
                if (this.#heap[rightChild] < this.#heap[min]) {
                    min = rightChild
                }
                this.swap(min, index);
                index = min;
                leftChild = this.leftChildIndex(min);
                rightChild = this.rightChildIndex(min);
            }
        }

        return item;
    }
}


// 힙 정렬
const heapSort = (arr, type) => {
    var result = [];
    var heap = new Heap(type);

    heap.insert(arr);
    for (let i = 0; i < arr.length; i++) {
        result.push(heap.delete());
    }
    return result;
}

// 임의 배열 생성
const makeRandomValueArr = (length) => {
    const arr = [];
    for (let i = 0; i < length; i++) {
        arr.push(i);
    }

    for (let i = 0; i < arr.length; i++) {
        const randomNum = Math.floor(Math.random() * arr.length);
        [arr[i], arr[randomNum]] = [arr[randomNum], arr[i]];
    }

    return arr;
}

// 결과

const minArr = makeRandomValueArr(10);
console.log('minArr==', minArr);
// minArr== (10) [2, 1, 8, 4, 6, 7, 3, 0, 9, 5]
console.time('min Heap');
const minResult = heapSort(minArr, 'min');
console.timeEnd('min Heap');
console.log('minResult==', minResult);
// minResult== (10) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

const maxArr = makeRandomValueArr(10);
console.log('maxArr==', maxArr);
// maxArr== (10) [8, 1, 0, 5, 2, 6, 7, 9, 4, 3]
console.time('max Heap');
const maxResult = heapSort(maxArr, 'max');
console.timeEnd('max Heap');
console.log('maxResult==', maxResult);
// maxResult== (10) [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

 

정렬에 대해 알면 알수록 정말

기발한 방법을 통해서 속도를 빠르게 하는 것 같습니다.