자료구조 힙(Heap)은? 무엇인가?

오늘은 자료구조 중 힙(Heap)을 알아보겠습니다. 

 

Heap이란 무엇인가?

 

힙은 자료구조 중 최댓값, 최소값을 가장 빨리 찾아내는 자료구조로 최댓값을 가장 빨리 찾아내는 힙은 "최대 힙", 최소값을 가장 빨리 찾아내는 힙은 "최소 힙"으로 두가지 종류의 힙이 있습니다. 

 

과연 힙은 어떤 구조로 이루어져 있으며, 어떻게 최댓값 or 최소값을 빠르게 찾아낼 수 있는지에 대해서 공부해보겠습니다.

 

마지막으로 힙을 활용한 자료구조인 우선순위 큐(Priority Queue)를 JavaScript를 활용하여 구현할 예정이니 끝까지 함께 공부하시면 감사하겠습니다.

 

 

Heap의 구조

힙은 완전 이진 트리구조로 이루어져 있습니다. 완전 이진 트리란 아래 그림과 같이 자식이 최대 두개인 트리 구조이며, 최하위 노드를 제외한 모든 노드들은 완전하게 두개씩 채워져 있는 트리입니다.

 

 

 

 

여기서 힙은 완전 이진 트리 구조에서 정렬된 데이터의 형태를 갖추고 있습니다.

 

 

최대 힙(Max Heap)은 트리의 최상단 노드에 가장 값이 큰 데이터가 존재하며, 큰 순서대로 왼쪽 자식, 오른쪽 자식 이렇게 채워져 값이 내림차순으로 정렬된 완전 이진 트리의 형태입니다.

 

 

 

 

 

 

최소 힙(Max Heap)은 트리의 최상단 노드에 가장 값이 작은 데이터가 존재하며, 아래로 작은 순서대로 왼쪽 자식, 오른쪽 자식 순서에 맞게 채워져 데이터 구조가 정렬되어있는 완전 이진 트리의 형태입니다.

 

 

 

 

 

 

Heap의 기능에 따른 동작

힙 자료구조는 최상단 노드의 값(최댓값 or 최소값)을 꺼내거나, 찾을 수 있으며, 노드를 삽입할 수 있습니다. 이 때, 힙 내에서 어떤 동작이 이루어지는지 확인해보겠습니다.

 

다음 Heap은 최소 힙(Min Heap)을 기준으로 설명하였습니다.

 

 

① 최상단 노드 보기

 

최상단 노드 보기는 정말 간단합니다. 힙은 항상 최상단 노드를 직접 탐색할 수 있기에, O(1)의 시간 복잡도로 탐색하여 값을 확인할 수 있습니다.

 

 

 

 

 

 

② 최상단 노드 꺼내 제거하기

 

최상단 노드 제거하기(반환하기)는 힙의 재정렬이 발생하는 동작입니다. 즉 최상단 노드를 제거하였을 경우, 다음 최상단 노드에 올라가야할 값을 탐색하고, 순차적으로 아래에 있는 데이터들이 올라가는 동작을 하게됩니다. 이 때 발생하는 시간복잡도는 O(logN)의 시간 복잡도를 갖습니다. 이유는 이진 트리로 되어있기에, 총 데이터 크기에 대하여 logN 만큼의 횟수로 동작하기 때문입니다.

 

 

①	②

③	④

 

 

위 그림을 순서대로 나열하면 다음과 같습니다.

1. 최상단 노드를 제거한다.
2. 마지막 노드를 최상단으로 이동한다.
3. 자식 노드 중 더 작은 값을 찾는다.
4. 찾은 자식 노드가 부모 노드보다 작으면 서로 교환한다.
5. 찾은 자식 노드가 부모 노드보다 작지 않으면 교환하지 않는다.
6. 교환된 노드를 부모 노드로 하여 3~5번을 반복한다.

 

 

 

 

③ 노드 삽입하기

 

노드 삽입하기는 또한 힙의 재정렬이 발생하는 동작입니다. 이 동작은 삽입되는 노드의 값이 힙의 어느 부분에 들어갈지를 먼저 계산하게 되고, 삽입될 위치를 확인하였을 경우 그 위치에 있던 노드들의 자리 이동이 일어나게 됩니다. 여기서 노드 삽입에도 불구하고 힙은 순서대로 정렬되어지는 구조를 갖출 수 있습니다. 이 때의 시간복잡도도 최상단 노드 제거하는 것과 같이 O(logN)입니다.

 

 

①	②
③	④

 

 

위 그림을 순서대로 나열하면 다음과 같습니다.

1. 마지막 노드로 삽입한다.
2. 삽입된 노드가 부모 노드보다 값이 작으면 교환한다.
3. 삽입된 노드가 부모 노드보다 값이 작지 않으면 교환하지 않는다.
4. 교환된 삽입 노드를 자식 노드로 하여 2~3번을 반복한다.

 

 

 

 

Heap의 구현

이번에는 자료구조 힙을 구현해보겠습니다. 힙 자료구조 구현은 JavaScript로 구현할 것입니다.

(JavaScript는 힙 자료구조를 제공해주지 않기에, JavaScript 언어로 개발을 할 때 필요에 따라 사용할 수 있도록 여기서 기능을 구현해보겠습니다.)

 

 

자료구조 힙을 구현할 때 활용하는 기본 자료구조는 배열을 통해 구현해보도록 하겠습니다.

또한, 힙을 활용하여 가장 많이 사용하는 자료구조인 우선순위 큐(Priority Queue)를 코드로 구현하면서 Heap에 대한 삽입/제거 기능을 코드로 확인해보겠습니다. 우선순위 큐는 최소 힙(Min Heap)을 활용하여 최상단 노드에 제일 작은 값이 있는 구조로 구현하겠습니다.

 

 

먼저 힙을 어떻게 배열에 데이터를 나열하는지부터 이해하고 넘어가겠습니다.

아래 그림은 완전 이진 트리 구조로 이루어진 힙의 구조를 배열에 어떤 방식으로 나열되는지 나타내는 그림입니다.

 

 

 

 

먼저 배열의 0번째 Index는 힙 자료구조로 구현될 때 활용되지 않습니다. 그 이유는 Index를 통한 부모/자식 노드 연결을 위해서이며, 연결 방법은 다음과 같습니다.

 

부모 노드의 왼쪽 자식 노드는 부모 노드의  배열 Index X 2이며, 오른쪽 자식 노드는 부모 노드의 배열 Index X 2 + 1로 데이터들이 힙 자료구조에 구성됩니다. 그럼 위 내용을 기반으로 Heap을 구현해보겠습니다.

 

 

 

 

Heap의 선언

    // 자료구조 Heap 선언
    #data = [];

    // Heap은 Index 0을 활용하지 않으므로, '-'로 입력하여 활용하지 않는 표시를 함.
    constructor() {
        this.#data.push('-');
    }

활용되는 자료구조는 배열이며, 맨 앞의 인덱스 0은 힙에서 활용하지 않으므로 '-'로 미리 입력해줍니다.

 

 

 

 

Heap의 삽입 기능 코드 구현

// Heap에서 삽입 API
add(value) {
    this.#data.push(value);

    this.#swapUp(this.#data.length - 1);
}

#swapUp(index) {
    let isChanged = false;
    let parentIndex = this.#getParentIndex(index);
    if(parentIndex === 0) {
        return;
    } 
        
    if(!this.#compare(parentIndex, index)) {
        isChanged = true;
        this.#swapValue(index, parentIndex);
    }

    if(isChanged) {
        this.#swapUp(parentIndex);
    }
}

 

 

 

 

Heap의 제거 기능 코드 구현

// Heap에서 제거 API
remove() {
    if (this.#data.length > 2) {
        this.#data[PRIORITY_QUEUE_FIRST_DATA_INDEX] = this.#data.pop();
        this.#swapDown(PRIORITY_QUEUE_FIRST_DATA_INDEX);
    } else if(this.#data.length === 2) {
        this.#data.pop();
    }
}
    
#swapDown(index) {
    let isChanged = false;
    let leftIndex = this.#getLeftIndex(index);
    let rightIndex = this.#getRightIndex(index);
    let curIndex = this.#compare(leftIndex, rightIndex) ? leftIndex : rightIndex;
        
    if(!this.#compare(index, curIndex)) {
        isChanged = true;
        this.#swapValue(index, curIndex);
    }

    if(isChanged) {
        this.#swapDown(curIndex);
    }
}

 

 

 

 

JavaScript로 구현한 Priority Queue(Heap) 코드

JavaScript로 Heap 자료구조을 활용한 대표적인 자료구조인 PriorityQueue를 구현해보았습니다.

(실제 구현한 PriorityQueue Class는 접어놓았으니 궁금하신 분은 열어서 한번 코드 확인해보시기 바랍니다.

const PRIORITY_QUEUE_FIRST_DATA_INDEX = 1
class PriorityQueue{
    #data = [];

    constructor() {
        this.#data.push('-');
    }
    
    print() {
        console.log(this.#data);
    }

    // Min Heap
    #compare(aIndex, bIndex) {
        if(!this.#data[aIndex] || !this.#data[bIndex]) {
            return true;
        }
        return this.#data[aIndex] < this.#data[bIndex];
    }

    #getParentIndex(index) {
        return Math.floor(index / 2);
    }

    #getLeftIndex(index) {
        return index * 2;
    }

    #getRightIndex(index) {
        return index * 2 + 1;
    }

    peek() {
        return this.#data.length > PRIORITY_QUEUE_FIRST_DATA_INDEX ? this.#data[PRIORITY_QUEUE_FIRST_DATA_INDEX] : null;
    }

    poll() {
        let pollData = this.peek();
        if (this.#data.length > 2) {
            this.#data[PRIORITY_QUEUE_FIRST_DATA_INDEX] = this.#data.pop();
            this.#swapDown(PRIORITY_QUEUE_FIRST_DATA_INDEX);
        } else if(this.#data.length === 2) {
            this.#data.pop();
        }

        return pollData;
    }
    
    #swapDown(index) {
        let isChanged = false;
        let leftIndex = this.#getLeftIndex(index);
        let rightIndex = this.#getRightIndex(index);
        let curIndex = this.#compare(leftIndex, rightIndex) ? leftIndex : rightIndex;
        
        if(!this.#compare(index, curIndex)) {
            isChanged = true;
            this.#swapValue(index, curIndex);
        }

        if(isChanged) {
            this.#swapDown(curIndex);
        }
    }

    #swapValue(aIndex, bIndex) {
        let value = this.#data[aIndex];
        this.#data[aIndex] = this.#data[bIndex];
        this.#data[bIndex] = value;
    }

    add(value) {
        this.#data.push(value);

        this.#swapUp(this.#data.length - 1);
    }

    #swapUp(index) {
        let isChanged = false;
        let parentIndex = this.#getParentIndex(index);
        if(parentIndex === 0) {
            return;
        } 
        
        if(!this.#compare(parentIndex, index)) {
            isChanged = true;
            this.#swapValue(index, parentIndex);
        }

        if(isChanged) {
            this.#swapUp(parentIndex);
        }
    }
}

 

 

 

 

오늘도 최댓값 or 최소값을 빠르게 가져올 수 있는 자료구조 Heap의 개념 및 삽입/제거의 기능에 대해 알아보았습니다. 또한, Heap을 활용하여 가장 많이 활용되는 자료구조 구현체인 우선순위 큐(Priority Queue)를 JavaScript로 구현해보았습니다.

 

다음엔 어떤 학습 내용으로 찾아올까요?