[Javascript] 자료구조 - Heap

 

 

1. Heap이란?

힙(Heap)은 자료구조의 한 종류로, 특정한 규칙을 가지는 이진 트리이다. 주로 우선순위 큐를 구현하는 데 사용된다. 힙은 완전 이진 트리의 일종으로 마지막 레벨을 제외한 모든 레벨에서 노드들이 완전히 채워져있고, 마지막 레벨의 노드들은 왼쪽부터 순서대로 채워져있다. 
힙의 각 노드는 일반적으로 부모 노드보다 더 높은 우선순위를 가지고 있다. 이를 최대 힙(Max Heap)이라고 한다. 반대로 각 노드는 부모 노드보다 더 낮은 우선순위를 가지고 있는데 이를 최소 힙(Min Heap)이라고 한다.

힙은 부모노드와 자식노드간의 우선순위 조건이 항상 유지되어야한다. 따라서 삽입이나 삭제연산을 할 때 힙속성을 유지해야한다. 
최대힙에서는 최대값을 빠르게 찾아야하며, 최소힙에서는 최소값을 빠르게 찾아야한다.

힙은 주로 우선순위 큐를 구현하는 데 사용되며, 힙을 이용하면 삽입, 삭제, 우선순위 변경 등의 연산을 O(log n)의 시간 복잡도로 수행할 수 있어서 효율적이다.

 

2. Heap을 사용하는 사례

힙 정렬도 힙이 사용된 정렬 방식으로 데이터를 효율적으로 정렬하는 데 사용된다. 힙 기반의 우선순위 큐(Priority Queue)는 가장 높은 (또는 가장 낮은) 우선순위를 가진 요소에 빠르게 접근할 수 있는 추상 자료형이다. 이는 작업 스케줄링, 이벤트 처리, 데이터 압축 등과 같은 분야에서 널리 사용된다. 메모리 할당과 해제와 같이 동적으로 메모리를 관리할 때 힙이 사용된다. 대부분의 프로그래밍 언어에서는 힙 메모리를 효과적으로 관리하기 위한 라이브러리 및 함수를 제공한다.

그래프 알고리즘에서도 다익스트라 알고리즘과 같은 최단 경로 찾기에 힙이 사용된다. 이를 통해 최소 거리를 빠르게 업데이트할 수 있어 그래프에서의 효율적인 경로 탐색이 가능하다. 최대 또는 최소 값을 찾는 문제에도 힙이 유용하다. 최대 힙은 최대 값을 찾는 데 사용되고, 최소 힙은 최소 값을 찾는 데 사용된다.

 

3. Javascript로 구현한 Heap

class MinHeap {
    constructor() {
        this.heap = [];
    }

    // 부모 인덱스를 반환하는 함수
    parent(index) {
        return Math.floor((index - 1) / 2);
    }

    // 왼쪽 자식 인덱스를 반환하는 함수
    leftChild(index) {
        return 2 * index + 1;
    }

    // 오른쪽 자식 인덱스를 반환하는 함수
    rightChild(index) {
        return 2 * index + 2;
    }

    // 힙에 요소를 삽입하는 함수
    insert(value) {
        this.heap.push(value);
        this.heapifyUp(this.heap.length - 1);
    }

    // 힙의 위쪽으로 요소를 올려 정렬하는 함수
    heapifyUp(index) {
        let currentIndex = index;
        while (currentIndex > 0 && this.heap[currentIndex] < this.heap[this.parent(currentIndex)]) {
            [this.heap[currentIndex], this.heap[this.parent(currentIndex)]] = [this.heap[this.parent(currentIndex)], this.heap[currentIndex]];
            currentIndex = this.parent(currentIndex);
        }
    }

    // 최소 요소를 반환하고 삭제하는 함수
    extractMin() {
        if (this.heap.length === 0) {
            return null;
        }
        if (this.heap.length === 1) {
            return this.heap.pop();
        }

        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown(0);
        return min;
    }

    // 힙의 아래쪽으로 요소를 내려 정렬하는 함수
    heapifyDown(index) {
        let smallest = index;
        const left = this.leftChild(index);
        const right = this.rightChild(index);
        const heapSize = this.heap.length;

        if (left < heapSize && this.heap[left] < this.heap[smallest]) {
            smallest = left;
        }

        if (right < heapSize && this.heap[right] < this.heap[smallest]) {
            smallest = right;
        }

        if (smallest !== index) {
            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            this.heapifyDown(smallest);
        }
    }

    // 힙을 출력하는 함수
    print() {
        console.log(this.heap);
    }
}

// 사용 예시
const minHeap = new MinHeap();
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(8);
minHeap.insert(1);
minHeap.insert(10);
minHeap.print(); // Output: [1, 3, 8, 5, 10]

console.log(minHeap.extractMin()); // Output: 1
minHeap.print(); // Output: [3, 5, 8, 10]

 

4. Javascript로 구현한 Heap 정렬

function heapSort(array) {
    // 힙을 구성
    function heapify(array, index, heapSize) {
        let largest = index;
        const left = 2 * index + 1;
        const right = 2 * index + 2;

        if (left < heapSize && array[left] > array[largest]) {
            largest = left;
        }

        if (right < heapSize && array[right] > array[largest]) {
            largest = right;
        }

        if (largest !== index) {
            [array[index], array[largest]] = [array[largest], array[index]];
            heapify(array, largest, heapSize);
        }
    }

    // 힙을 구성
    function buildHeap(array) {
        const heapSize = array.length;
        for (let i = Math.floor(heapSize / 2); i >= 0; i--) {
            heapify(array, i, heapSize);
        }
    }

    // 정렬
    function sort(array) {
        buildHeap(array);
        let heapSize = array.length;
        for (let i = array.length - 1; i > 0; i--) {
            [array[0], array[i]] = [array[i], array[0]];
            heapSize--;
            heapify(array, 0, heapSize);
        }
    }

    sort(array);
    return array;
}

// 사용 예시
const arr = [6, 10, 2, 9, 5, 1, 8, 3, 7, 4];
console.log(heapSort(arr)); // Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 

4. Python으로 구현한 Heap

class MinHeap:
    def __init__(self):
        self.heap = []

    # 부모 노드의 인덱스를 반환하는 함수
    def parent(self, index):
        return (index - 1) // 2

    # 왼쪽 자식 노드의 인덱스를 반환하는 함수
    def left_child(self, index):
        return 2 * index + 1

    # 오른쪽 자식 노드의 인덱스를 반환하는 함수
    def right_child(self, index):
        return 2 * index + 2

    # 요소를 삽입하는 함수
    def insert(self, value):
        self.heap.append(value)
        self.heapify_up(len(self.heap) - 1)

    # 힙의 위쪽으로 요소를 올려 정렬하는 함수
    def heapify_up(self, index):
        while index > 0 and self.heap[index] < self.heap[self.parent(index)]:
            self.heap[index], self.heap[self.parent(index)] = self.heap[self.parent(index)], self.heap[index]
            index = self.parent(index)

    # 최소 요소를 추출하고 삭제하는 함수
    def extract_min(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        min_value = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.heapify_down(0)
        return min_value

    # 힙의 아래쪽으로 요소를 내려 정렬하는 함수
    def heapify_down(self, index):
        smallest = index
        left = self.left_child(index)
        right = self.right_child(index)
        heap_size = len(self.heap)

        if left < heap_size and self.heap[left] < self.heap[smallest]:
            smallest = left

        if right < heap_size and self.heap[right] < self.heap[smallest]:
            smallest = right

        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self.heapify_down(smallest)

    # 힙을 출력하는 함수
    def print_heap(self):
        print(self.heap)

# 사용 예시
min_heap = MinHeap()
min_heap.insert(5)
min_heap.insert(3)
min_heap.insert(8)
min_heap.insert(1)
min_heap.insert(10)
min_heap.print_heap()  # Output: [1, 3, 8, 5, 10]

print(min_heap.extract_min())  # Output: 1
min_heap.print_heap()  # Output: [3, 5, 8, 10]

 

5. Python으로 구현한 Heap정렬

def heap_sort(array):
    # 힙을 구성하는 함수
    def heapify(array, n, i):
        largest = i  # 루트 노드
        left = 2 * i + 1  # 왼쪽 자식 노드
        right = 2 * i + 2  # 오른쪽 자식 노드

        # 왼쪽 자식 노드가 존재하고 루트보다 크다면
        if left < n and array[left] > array[largest]:
            largest = left

        # 오른쪽 자식 노드가 존재하고 루트보다 크다면
        if right < n and array[right] > array[largest]:
            largest = right

        # 최대값이 루트가 아니라면 교환
        if largest != i:
            array[i], array[largest] = array[largest], array[i]
            heapify(array, n, largest)

    n = len(array)

    # 힙을 구성
    for i in range(n // 2 - 1, -1, -1):
        heapify(array, n, i)

    # 요소를 하나씩 꺼내 정렬
    for i in range(n - 1, 0, -1):
        array[i], array[0] = array[0], array[i]  # 최대값을 마지막 노드와 교환
        heapify(array, i, 0)  # 교환된 부분의 힙을 재구성

    return array

# 사용 예시
arr = [6, 10, 2, 9, 5, 1, 8, 3, 7, 4]
print(heap_sort(arr))  # Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]