[자료구조] 힙(Heap)

✅ 힙(Heap)이란?

힙(Heap)은 자료 구조 중 하나로, 일반적으로 우선순위 큐(Priority Queue)를 구현하는 데 사용된다. 힙은 완전 이진트리(Complete Binary Tree) 구조를 가지며, 부모 노드와 자식 노드 간에 우선순위 관계를 가진다.

* 완전 이진트리 - 모든 노드가 왼쪽 자식과 오른쪽 자식을 가진 이진트리로서, 마지막 레벨을 제외한 모든 레벨이 꽉 차 있는 이진트리를 말한다. 마지막 레벨은 왼쪽에서부터 오른쪽으로 채워지는 형태이다.

🟢이진 힙(Binary Heap)

힙의 한 종류로, 모든 노드는 최대 두 개의 자식 노드를 가지며, 주로 배열을 사용하여 구현된다.

🟡 이진 힙의 두 종류

최대 힙(Max Heap): 부모 노드는 자식 노드보다 항상 크거나 같은 값을 가짐.
최소 힙(Min Heap): 부모 노드는 자식 노드보다 항상 작거나 같은 값을 가짐.

힙의 주요 연산은 삽입, 삭제, 최대/최솟값 검색 등이 있다. 삽입 연산은 힙의 끝에 새로운 값을 삽입한 후, 부모 노드와 비교하면서 위치를 조정하고 삭제 연산은 항상 최상위 노드(루트 노드)를 삭제하며, 이후에 힙의 규칙을 유지하도록 자식 노드와 위치를 변경한다.

출처: https://www.geeksforgeeks.org/heap-data-structure/

노드 n의 부모 노드는 (n-1)/2 내림, 왼쪽 자식 노드는 2n+1, 오른쪽 자식 노드는 2n+2의 인덱스를 갖는 규칙을 가지고 있다. 

🤔 최대 이진 힙 구현하기

🟡 Insert 의사코드

• 힙의 value 속성에 값을 넣어라.
• Bubble Up:
  • index라는 변수를 만들고, 배열의 맨 뒤에 있는 요소를 저장한다.
  • parentIndex라는 변수를 만들고, 부모의 자리를 찾는다. floor of (index-1)/2
  • parentIndex의 값 요소가 하위 인덱스의 값 요소보다 작으면 아래의 작업을 계속 반복한다.
    • 해당 인덱스에 있는 값과 배열 맨 뒤에 추가한 값과 비교하여 어느 것이 더 큰지 확인한다.
    • 추가한 값이 더 크다면 두 값의 자리를 스왑. 그렇지 않다면 멈춘다.

class MaxBinaryHeap {
    constructor() {
        this.values = [41, 39, 33, 18, 27, 12];
    }

    insert(element) {
        this.values.push(element);
        this.bubbleUp();
    }
    bubbleUp() {
        let idx = this.values.length - 1;
        const element = this.values[idx];
        while (idx > 0) {
            let parentIdx = Math.floor((idx - 1) / 2);
            let parent = this.values[parentIdx];
            if (element <= parent) break;
            this.values[parentIdx] = element;
            this.values[idx] = parent;
            idx = parentIdx;
        }
    }
}

let heap = new MaxBinaryHeap();
heap.insert(55)

// [41, 39, 33, 18, 27, 12]
//   0   1   2   3   4   5

🟡 remove 의사코드 ( 메서드명 - extracMax) 

최대 힙에서 삭제는 최대 값 즉, 루트 노드를 제거한다. 가장 맨 뒤에 있는 값을 루트로 만들고, bubble-down(혹은 sift-down, sink-down, percolate-down 등)으로 제자리에 위치하게 한다.  

• value 속성의 첫 번째 값(루트)과  마지막 값을 스왑 한다.
• value 속성에서 pop 하여, 끝에 있는 값을 반환한다.
• 새 루트를 올바른 위치에 "sink down" 시킨다.
  • parent index는 0에서 시작한다.
  • 왼쪽 자식의 인덱스 찾기: 2 * index + 1(경계를 벗어나지 않는지 확인)
  • 오른쪽 자식의 인덱스 찾기: 2 * index + 2(경계를 벗어나지 않는지 확인)
  • 만약 왼쪽 혹은 오른쪽 자식이 요소보다 더 큰 경우 스왑. 만약 둘 다 자식이 더 큰 경우 가장 큰 자식과 스왑.
  • 이제 스왑 한 자식 index가 새 부모 index가 된다.
  • 어떤 자식도 요소보다 크지 않을 때까지 루프와 스왑을 계속한다.
  • 이전 루트를 반환한다.

extractMax() {
        const max = this.values[0];
        const end = this.values.pop();
        // 요소가 없을 경우 return
        if (this.values.length > 0) {
            // root 자리에 가장 최근에 삽입됐던 end를 넣고
            this.values[0] = end;
            // root 자리에 올라간 end의 sinkDown()을 시작
            this.sinkDown();
        }
        return max;
    }

    sinkDown() {
        let idx = 0;
        const length = this.values.length;
        while (true) {
            // sinkDown할 주인공 element 변수 설정
            const element = this.values[idx];
            // 부모 위치로부터 자식 위치 찾는 공식을 이용해서 left, right 자식의 위치를 구함. 
            const leftChildIdx = 2 * idx + 1;
            const rightChildIdx = 2 * idx + 2;
            let leftChild;
            let rightChild;
            let swap = null;
            // 찾은 자식의 인덱스가 실제로 존재할 때에만, 그 값을 변수로 할당. 
            // 먼저 leftChild 변수가 element와 비교해서 더 크다면, 그 인덱스를 swap에 할당. 
            if (leftChildIdx < length) {
                leftChild = this.values[leftChildIdx];
                if (leftChild > element) {
                    swap = leftChildIdx;
                }
            }

            if (rightChildIdx < length) {
                rightChild = this.values[rightChildIdx];
                if ((swap === null && rightChild > element) || (swap !== null && rightChild > leftChild)) {
                    swap = rightChildIdx;
                }
            }
            // 만약 여전히 swap이 null이면 element는 이미 제 자리에 있는 것이므로 반복문을 break
            if (swap === null)
                break;

            // 그렇지 않고 swap 값이 있다면, element와 swap할 대상의 자리를 서로 바꿈.
            [this.values[idx],this.values[swap]] = [this.values[swap], this.values[idx]];
            // while문의 다음 턴에서 사용할 element의 새 인덱스를 swap으로 재할당해서 최신화해준다.
            idx = swap;
        }
    }

✅ 우선순위 큐(Priority Queue)란?

일반적인 큐와 달리 각각의 요소에 우선순위가 있다. 요소가 큐에 추가되는 순서는 상관없이, 우선순위가 높은 요소는 항상 먼저 제거된다.

즉, 큐에 추가될 때 우선순위가 낮은 요소가 먼저 들어가고, 우선순위가 높은 다른 요소가 큐에 나중에 추가(Enqueue)되면, 우선순위가 높은 요소가 먼저 제거(Dequeue)된다.

class Node {
    constructor(val, priority) {
        this.val = val;
        this.priority = priority;
    }
}

class PriorityQueue {
    constructor() {
        this.values = [];
    }

    enqueue(val, priority) {
        let newNode = new Node(val,priority);
        this.values.push(newNode)
        this.bubbleUp();
    }
    bubbleUp() {
        let idx = this.values.length - 1;
        const element = this.values[idx];
        while (idx > 0) {
            let parentIdx = Math.floor((idx - 1) / 2);
            let parent = this.values[parentIdx];
            if (element.priority <= parent.priority)
                break;
            this.values[parentIdx] = element;
            this.values[idx] = parent;
            idx = parentIdx;
        }
    }
    dequeue() {
        const max = this.values[0];
        const end = this.values.pop();
        if (this.values.length > 0) {
            this.values[0] = end;
            this.sinkDown();
        }
        return max;
    }

    sinkDown() {
        let idx = 0;
        const length = this.values.length;
        while (true) {
            const element = this.values[idx];
            const leftChildIdx = 2 * idx + 1;
            const rightChildIdx = 2 * idx + 2;
            let leftChild;
            let rightChild;
            let swap = null;

            if (leftChildIdx < length) {
                leftChild = this.values[leftChildIdx];
                if (leftChild.priority > element.priority) {
                    swap = leftChildIdx;
                }
            }

            if (rightChildIdx < length) {
                rightChild = this.values[rightChildIdx];
                if ((swap === null && rightChild.priority > element.priority) || (swap !== null && rightChild.priority > leftChild.priority)) {
                    swap = rightChildIdx;
                }
            }
            if (swap === null)
                break;

            [this.values[idx],this.values[swap]] = [this.values[swap], this.values[idx]];
            idx = swap;
        }
    }
}

let ER = new PriorityQueue();

이진 힙의 빅오

Insertion - O(log N)

Removal - O(log N)

Search - O(N)

 

이진 힙은 힙의 한 종류이고, 힙은 트리의 한 종류인 셈이다.

 

정리하자면,

• 이진 힙은 정렬 및 우선순위 큐와 같은 데이터 구조를 구현하는 데 유용한 데이터 구조이다.
• 힙에는 최대 힙과 최소 힙이 있다. 항상 왼쪽에서 오른쪽으로 채운다.
• 약간의 수학 공식을 사용하면 배열을 가지고 힙을 쉽게 표현할 수 있다.