[자료구조] 이진 힙(binary heap) 그리고 힙 정렬(heap sort)

참고

 - https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

소스코드

heap.zip

사용하실 때, 댓글을 남겨주세요.

정의

 힙은 2진 힙(바이너리 힙)이라고도 부르며 최댓값과 최솟값 찾기 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조로써 다음과 같은 힙 속성(property)을 만족합니다.

 - A가 B의부모노드(parent node)이면 A의 키(key)값과 B의 키 값 사이에는 대소관계가 성립한다.

최대 힙

 - 부모노드의 키값이 자식 노드의 키값보다 항상 큰 힙

최소 힙

 - 부모노드의 키값이 자식 노드의 키값보다 항상 작은 힙

형제 사이에는 대소관계가 정해지지 않습니다.

(Max heap 이미지입니다.)

Push

 힙에 값을 추가하는 함수입니다.

this.push = function(value)
{
    arr[count] = value;
    var child = count;
 
    while(child > 0)
    {
        var parent = Math.floor((child + 1) * 0.5) - 1;
        if(compare(arr[child], arr[parent]))
        {
            swap(parent, child);
            child = parent;
        }
        else
            break;
    }
 
    ++count;
}

규칙

1. 마지막에 값을 추가합니다.
2. 부모와 비교하여 부모보다 크면(최소힙은 부모보다 작으면) 부모와 swap합니다.
3. 부모보다 작을때까지 혹은 최상단(0번 인덱스)이 될 때까지(최소힙은 부모보다 클때까지 2번을 반복합니다.

Pop

 힙에서 값을 가져오는 함수입니다.

this.pop = function()
{
    if(count === 0)
        return null;
 
    var ret = arr[0];
    arr[0] = arr[count-1];
 
    --count;
 
    var node = 0;
    while(true)
    {
        var child1 = node * 2 + 1;
        var child2 = child1 + 1;
 
        var swapIdx = node;
        if(child1 < count && compare(arr[child1], arr[swapIdx]))
            swapIdx = child1;
        if(child2 < count && compare(arr[child2], arr[swapIdx]))
            swapIdx = child2;
 
        if(swapIdx !== node)
        {
            swap(node, swapIdx);
            node = swapIdx;
        }
        else
            break;
    }
 
    return ret;
}

규칙

1. 최상단(0번인덱스)를 빼냅니다.
2. 최상단에 배열의 마지막 데이터를 집어넣습니다.
3. 자식과 비교하여 자신보다 크면 교체(최소힙일 경우 작으면)합니다.(둘 다 클 경우, 가장 큰 자식과 교체합니다.)
4. 자식보다 작아질때(최소힙일 경우 커질때)까지 혹은 자식이 없어질 때까지 3번을 반복합니다.

이렇게 추출할 경우, 정렬된 데이터를 추출해낼 수 있습니다.

추가적으로

 보편적으로 compare함수를 생성자에서 전달받아 사용합니다.

 예를들어 int나 float이 아닌 사용자정의 형일 경우, 크거나 작은것을 비교할 수 없습니다. 그렇기 때문에 사용자정의 compare함수를 전달받아 사용하게 됩니다.

힙 정렬

 위에서 설명드린 힙을 이용해 정렬하는 알고리즘입니다.

제자리 정렬 알고리즘에 의 시간복잡도를 가지고 있습니다.

{
    // (1) 힙 형태로 정렬
    for (var i = Math.floor(this.nodes.length * 0.5) - 1 ; i >= 0 ; --i)
    {
        var parent = i;
        while(true)
        {
            var child1 = parent * 2 + 1;
            var child2 = child1 + 1;
 
            var changeIndex = parent;
            if (child1 < this.nodes.length &&
                compare(this.nodes[child1], this.nodes[changeIndex]))
                changeIndex = child1;
            if (child2 < this.nodes.length &&
                compare(this.nodes[child2], this.nodes[changeIndex]))
                changeIndex = child2;
 
            if(changeIndex !== parent)
            {
                this.swap(parent, changeIndex);
                parent = changeIndex;
            }
            else
                break;
        }
    }
 
    // (2) 최상위 값을 빼와서 뒤에서부터 순서대로 삽입
    for (var i = 0 ; i < this.nodes.length ; ++i)
    {
        var last = this.nodes.length - 1 - i;
        var front = this.pop(last);
 
        this.nodes[last] = front;
        this.nodes[last].value.position.x = 5 + last * 55;
        this.nodes[last].value.position.y = 600;
    }
}
 

(1) 힙 형태로 정렬

 일단 배열을 힙형태로 정렬을 해야합니다.

이때, 정렬은 자식을 가지고 있는 Math.floor(this.nodes.length * 0.5) - 1번째 인덱스부터 역순으로 정렬해 나갑니다.

(2) 최상위 값을 빼와서 뒤에서부터 순서대로 삽입

 제자리 정렬을 해야하기 때문에 힙용 배열을 따로 만드는 것이 아니라 맨 첫번째 있는 것을 pop하여 끝에 집어넣습니다.

this.prototype.pop = function(last)
{
    var ret = this.nodes[0];
 
    this.nodes[0] = this.nodes[last];
    this.nodes[0].value.position.x = 5;
    this.nodes[0].value.position.y = 600;
 
    if(last <= 1)
        return ret;
 
    var parent = 0;
    while(true)
    {
        var child1 = parent * 2 + 1;
        var child2 = child1 + 1;
 
        var changeIndex = parent;
        if (child1 < last &&
            compare(this.nodes[child1], this.nodes[changeIndex]))
            changeIndex = child1;
        if (child2 < last &&
            compare(this.nodes[child2], this.nodes[changeIndex]))
            changeIndex = child2;
 
        if(changeIndex !== parent)
        {
            this.swap(parent, changeIndex);
            parent = changeIndex;
        }
        else
            break;
    }
 
    return ret;
}
 

pop함수는 위와 동일한 형태로 다른 부분은 last를 인자로 받아오는 것 외에는 없습니다.