힙(Heap): 효율적인 우선순위 관리와 정렬을 위한 자료구조

 

힙(Heap)은 완전 이진 트리를 기반으로 한 자료구조로, 특정 규칙을 만족하는 노드 간의 관계를 유지하여 우선순위 기반의 데이터 관리를 가능하게 합니다. 주로 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 구분되며, 최대 힙에서는 부모 노드가 자식 노드보다 크거나 같고, 최소 힙에서는 부모 노드가 자식 노드보다 작거나 같습니다. 힙은 효율적인 우선순위 큐 구현과 힙 정렬(Heap Sort) 알고리즘의 핵심 자료구조로 활용됩니다.

 

힙의 등장 배경

 

데이터를 우선순위에 따라 효율적으로 관리하고자 하는 실무적 요구가 증가함에 따라 힙 자료구조가 개발되었습니다. 힙은 삽입과 삭제 연산이 효율적으로 이루어지며, 우선순위 큐의 구현에 이상적인 자료구조로 자리 잡았습니다. 또한, 힙을 기반으로 한 힙 정렬 알고리즘은 비교 기반 정렬 알고리즘 중 하나로 널리 사용됩니다.

 

힙은 우선순위 큐 구현, 힙 정렬, 실시간 데이터 처리, 네트워크 트래픽 관리 등 다양한 실무 분야에서 핵심적으로 사용됩니다. 이 글에서는 힙의 기본 개념부터 실제 구현, 응용 예제까지 폭넓게 다루어 보겠습니다.

 

 

 

---

 

힙(Heap)의 개념

 

힙은 완전 이진 트리의 형태를 가지며, 힙 속성(Heap Property)을 만족하는 자료구조입니다. 힙 속성은 다음과 같습니다:

• 최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
• 최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같다.

힙은 배열을 이용하여 효율적으로 구현할 수 있으며, 부모 노드와 자식 노드 간의 인덱스 관계를 활용합니다.

 

힙의 특징

• 완전 이진 트리: 힙은 완전 이진 트리의 형태를 가지므로, 노드의 삽입과 삭제가 배열 인덱스를 통해 효율적으로 이루어집니다.
• 힙 속성: 최대 힙과 최소 힙의 속성을 통해 우선순위에 따른 데이터 관리가 가능합니다.
• 높이: 힙의 높이는 O(log n)으로, 삽입과 삭제 연산의 시간 복잡도를 O(log n)으로 유지할 수 있습니다.

 

힙의 응용 분야

• 우선순위 큐(Priority Queue): 우선순위에 따라 데이터를 처리하는 큐의 구현에 사용됩니다.
• 힙 정렬(Heap Sort): 힙을 기반으로 한 효율적인 정렬 알고리즘입니다.
• 그래프 알고리즘: 다익스트라 알고리즘과 같은 최단 경로 알고리즘에서 우선순위 큐로 힙이 사용됩니다.
• 실시간 데이터 처리: 실시간으로 데이터를 처리해야 하는 시스템에서 힙을 활용하여 우선순위에 따라 데이터를 관리합니다.

 

---

 

힙의 사용 사례

 

우선순위 큐(Priority Queue)

우선순위 큐는 큐의 일종으로, 각 요소가 우선순위를 가지며 우선순위가 높은 요소가 먼저 처리됩니다. 힙은 우선순위 큐의 구현에 이상적인 자료구조로, 삽입과 삭제 연산이 효율적으로 이루어집니다.

 

힙 정렬(Heap Sort)

힙 정렬은 힙 자료구조를 활용한 비교 기반의 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정적인 정렬 성능을 제공합니다. 힙 정렬은 정렬된 배열을 구성하는 데 힙을 반복적으로 재구성하여 요소를 추출합니다.

 

다익스트라 알고리즘(Dijkstra's Algorithm)

다익스트라 알고리즘은 그래프에서 최단 경로를 찾는 알고리즘으로, 우선순위 큐를 사용하여 현재까지의 최단 거리를 관리합니다. 힙을 사용한 우선순위 큐는 알고리즘의 효율성을 크게 향상시킵니다.

 

실시간 데이터 처리

실시간 시스템에서는 데이터를 우선순위에 따라 빠르게 처리해야 합니다. 힙은 우선순위 큐의 효율적인 구현을 통해 실시간 데이터 처리를 지원합니다.

 

 

---

 

힙(Heap) 구현하기

 

힙은 배열을 이용하여 효율적으로 구현할 수 있습니다. 

 

Python으로 힙(Heap) 구현하기

Python에서는 heapq 모듈을 사용하여 최소 힙을 쉽게 구현할 수 있습니다. 하지만 여기서는 힙의 원리를 이해하기 위해 최대 힙과 최소 힙을 직접 구현해 보겠습니다.

최대 힙(Max Heap) 구현

class MaxHeap:
    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, key):
        self.heap.append(key)  # 힙의 끝에 새로운 요소 추가
        self._heapify_up(len(self.heap) - 1)  # 힙 속성 유지

    def _heapify_up(self, index):
        while index != 0 and self.heap[self.parent(index)] < self.heap[index]:
            # 부모 노드와 현재 노드의 값을 교환
            self.heap[self.parent(index)], self.heap[index] = self.heap[index], self.heap[self.parent(index)]
            index = self.parent(index)  # 부모 노드로 이동

    def extract_max(self):
        if not self.heap:
            raise IndexError("extract_max from empty heap")
        if len(self.heap) == 1:
            return self.heap.pop()
        root = self.heap[0]  # 루트 노드(최대값) 저장
        self.heap[0] = self.heap.pop()  # 마지막 노드를 루트로 이동
        self._heapify_down(0)  # 힙 속성 유지
        return root

    def _heapify_down(self, index):
        size = len(self.heap)
        while True:
            largest = index
            left = self.left_child(index)
            right = self.right_child(index)

            if left < size and self.heap[left] > self.heap[largest]:
                largest = left
            if right < size and self.heap[right] > self.heap[largest]:
                largest = right
            if largest != index:
                self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
                index = largest
            else:
                break

    def peek_max(self):
        if not self.heap:
            raise IndexError("peek_max from empty heap")
        return self.heap[0]

    def size(self):
        return len(self.heap)

    def is_empty(self):
        return len(self.heap) == 0

    def display_heap(self):
        print(self.heap)

# 최대 힙 사용 예시
if __name__ == "__main__":
    max_heap = MaxHeap()
    elements = [10, 4, 15, 20, 0, 8]
    for el in elements:
        max_heap.insert(el)
    print("Max Heap:", max_heap.heap)  # 출력: Max Heap: [20, 10, 15, 4, 0, 8]

    print("Extract Max:", max_heap.extract_max())  # 출력: Extract Max: 20
    print("Heap after extracting max:", max_heap.heap)  # 출력: Heap after extracting max: [15, 10, 8, 4, 0]

    print("Peek Max:", max_heap.peek_max())  # 출력: Peek Max: 15

코드 설명

1. MaxHeap 클래스:
   • init 메서드:
     • self.heap는 힙을 저장하는 리스트입니다.
   • parent, left_child, right_child 메서드:
     • 주어진 인덱스의 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드의 인덱스를 계산합니다.
   • insert 메서드:
     • 새로운 키를 힙의 끝에 추가한 후, _heapify_up 메서드를 호출하여 힙 속성을 유지합니다.
   • _heapify_up 메서드:
     • 새로운 요소를 힙의 위로 이동시켜 힙 속성을 유지합니다.
     • 부모 노드의 값이 현재 노드의 값보다 작으면 두 값을 교환하고, 부모 노드로 이동하여 반복합니다.
   • extract_max 메서드:
     • 힙의 루트 노드(최댓값)를 추출합니다.
     • 마지막 노드를 루트로 이동시킨 후, _heapify_down 메서드를 호출하여 힙 속성을 유지합니다.
   • _heapify_down 메서드:
     • 루트 노드에서 시작하여 힙 속성을 유지하기 위해 아래로 이동합니다.
     • 현재 노드의 자식 노드들과 비교하여 가장 큰 값을 가진 노드와 교환합니다.
   • peek_max 메서드:
     • 힙의 루트 노드(최댓값)를 반환합니다.
   • size, is_empty, display_heap 메서드:
     • 힙의 크기 확인, 비어있는지 확인, 힙의 현재 상태를 출력하는 유틸리티 메서드입니다.
2. 사용 예시:
   • 힙에 여러 요소를 삽입하고, 최댓값을 추출한 후 힙의 상태를 출력합니다.
   • 힙 속성이 올바르게 유지되는지 확인할 수 있습니다.

 

최소 힙(Min 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, key):
        self.heap.append(key)  # 힙의 끝에 새로운 요소 추가
        self._heapify_up(len(self.heap) - 1)  # 힙 속성 유지

    def _heapify_up(self, index):
        while index != 0 and self.heap[self.parent(index)] > self.heap[index]:
            # 부모 노드와 현재 노드의 값을 교환
            self.heap[self.parent(index)], self.heap[index] = self.heap[index], self.heap[self.parent(index)]
            index = self.parent(index)  # 부모 노드로 이동

    def extract_min(self):
        if not self.heap:
            raise IndexError("extract_min from empty heap")
        if len(self.heap) == 1:
            return self.heap.pop()
        root = self.heap[0]  # 루트 노드(최소값) 저장
        self.heap[0] = self.heap.pop()  # 마지막 노드를 루트로 이동
        self._heapify_down(0)  # 힙 속성 유지
        return root

    def _heapify_down(self, index):
        size = len(self.heap)
        while True:
            smallest = index
            left = self.left_child(index)
            right = self.right_child(index)

            if left < size and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < 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]
                index = smallest
            else:
                break

    def peek_min(self):
        if not self.heap:
            raise IndexError("peek_min from empty heap")
        return self.heap[0]

    def size(self):
        return len(self.heap)

    def is_empty(self):
        return len(self.heap) == 0

    def display_heap(self):
        print(self.heap)

# 최소 힙 사용 예시
if __name__ == "__main__":
    min_heap = MinHeap()
    elements = [10, 4, 15, 20, 0, 8]
    for el in elements:
        min_heap.insert(el)
    print("Min Heap:", min_heap.heap)  # 출력: Min Heap: [0, 4, 8, 20, 10, 15]

    print("Extract Min:", min_heap.extract_min())  # 출력: Extract Min: 0
    print("Heap after extracting min:", min_heap.heap)  # 출력: Heap after extracting min: [4, 10, 8, 20, 15]

    print("Peek Min:", min_heap.peek_min())  # 출력: Peek Min: 4

코드 설명

1. MinHeap 클래스:
   • init 메서드:
     • self.heap는 힙을 저장하는 리스트입니다.
   • parent, left_child, right_child 메서드:
     • 주어진 인덱스의 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드의 인덱스를 계산합니다.
   • insert 메서드:
     • 새로운 키를 힙의 끝에 추가한 후, _heapify_up 메서드를 호출하여 힙 속성을 유지합니다.
   • _heapify_up 메서드:
     • 새로운 요소를 힙의 위로 이동시켜 힙 속성을 유지합니다.
     • 부모 노드의 값이 현재 노드의 값보다 크면 두 값을 교환하고, 부모 노드로 이동하여 반복합니다.
   • extract_min 메서드:
     • 힙의 루트 노드(최솟값)를 추출합니다.
     • 마지막 노드를 루트로 이동시킨 후, _heapify_down 메서드를 호출하여 힙 속성을 유지합니다.
   • _heapify_down 메서드:
     • 루트 노드에서 시작하여 힙 속성을 유지하기 위해 아래로 이동합니다.
     • 현재 노드의 자식 노드들과 비교하여 가장 작은 값을 가진 노드와 교환합니다.
   • peek_min 메서드:
     • 힙의 루트 노드(최솟값)를 반환합니다.
   • size, is_empty, display_heap 메서드:
     • 힙의 크기 확인, 비어있는지 확인, 힙의 현재 상태를 출력하는 유틸리티 메서드입니다.
2. 사용 예시:
   • 힙에 여러 요소를 삽입하고, 최솟값을 추출한 후 힙의 상태를 출력합니다.
   • 힙 속성이 올바르게 유지되는지 확인할 수 있습니다.

 

 

JavaScript으로 힙(Heap) 구현하기

 

JavaScript에서는 힙을 직접 구현해야 합니다. 아래는 최대 힙(Max Heap)과 최소 힙(Min Heap)을 각각 구현한 예제입니다. 힙의 기본 원리를 이해할 수 있도록 자세히 설명하겠습니다.

최대 힙(Max Heap) 구현

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

    parent(index) {
        return Math.floor((index - 1) / 2);
    }

    leftChild(index) {
        return 2 * index + 1;
    }

    rightChild(index) {
        return 2 * index + 2;
    }

    insert(key) {
        this.heap.push(key); // 힙의 끝에 새로운 요소 추가
        this.heapifyUp(this.heap.length - 1); // 힙 속성 유지
    }

    heapifyUp(index) {
        while (index > 0 && this.heap[this.parent(index)] < this.heap[index]) {
            // 부모 노드와 현재 노드의 값을 교환
            [this.heap[this.parent(index)], this.heap[index]] = [this.heap[index], this.heap[this.parent(index)]];
            index = this.parent(index); // 부모 노드로 이동
        }
    }

    extractMax() {
        if (this.heap.length === 0) {
            throw new Error("extractMax from empty heap");
        }
        if (this.heap.length === 1) {
            return this.heap.pop();
        }
        const root = this.heap[0]; // 루트 노드(최대값) 저장
        this.heap[0] = this.heap.pop(); // 마지막 노드를 루트로 이동
        this.heapifyDown(0); // 힙 속성 유지
        return root;
    }

    heapifyDown(index) {
        const size = this.heap.length;
        while (true) {
            let largest = index;
            const left = this.leftChild(index);
            const right = this.rightChild(index);

            if (left < size && this.heap[left] > this.heap[largest]) {
                largest = left;
            }

            if (right < size && this.heap[right] > this.heap[largest]) {
                largest = right;
            }

            if (largest !== index) {
                // 현재 노드와 가장 큰 자식 노드의 값을 교환
                [this.heap[largest], this.heap[index]] = [this.heap[index], this.heap[largest]];
                index = largest; // 교환된 자식 노드로 이동
            } else {
                break; // 힙 속성이 유지되면 종료
            }
        }
    }

    peekMax() {
        if (this.heap.length === 0) {
            throw new Error("peekMax from empty heap");
        }
        return this.heap[0];
    }

    size() {
        return this.heap.length;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    displayHeap() {
        console.log(this.heap);
    }
}

// 최대 힙 사용 예시
const maxHeap = new MaxHeap();
const elements = [10, 4, 15, 20, 0, 8];
for (let el of elements) {
    maxHeap.insert(el);
}
console.log("Max Heap:", maxHeap.heap); // 출력: Max Heap: [20, 10, 15, 4, 0, 8]

console.log("Extract Max:", maxHeap.extractMax()); // 출력: Extract Max: 20
console.log("Heap after extracting max:", maxHeap.heap); // 출력: Heap after extracting max: [15, 10, 8, 4, 0]

console.log("Peek Max:", maxHeap.peekMax()); // 출력: Peek Max: 15

코드 설명

1. MaxHeap 클래스:
   • constructor 메서드:
     • this.heap는 힙을 저장하는 배열입니다.
   • parent, leftChild, rightChild 메서드:
     • 주어진 인덱스의 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드의 인덱스를 계산합니다.
   • insert 메서드:
     • 새로운 키를 힙의 끝에 추가한 후, heapifyUp 메서드를 호출하여 힙 속성을 유지합니다.
   • heapifyUp 메서드:
     • 새로운 요소를 힙의 위로 이동시켜 힙 속성을 유지합니다.
     • 부모 노드의 값이 현재 노드의 값보다 작으면 두 값을 교환하고, 부모 노드로 이동하여 반복합니다.
   • extractMax 메서드:
     • 힙의 루트 노드(최댓값)를 추출합니다.
     • 마지막 노드를 루트로 이동시킨 후, heapifyDown 메서드를 호출하여 힙 속성을 유지합니다.
   • heapifyDown 메서드:
     • 루트 노드에서 시작하여 힙 속성을 유지하기 위해 아래로 이동합니다.
     • 현재 노드의 자식 노드들과 비교하여 가장 큰 값을 가진 노드와 교환합니다.
   • peekMax 메서드:
     • 힙의 루트 노드(최댓값)를 반환합니다.
   • size, isEmpty, displayHeap 메서드:
     • 힙의 크기 확인, 비어있는지 확인, 힙의 현재 상태를 출력하는 유틸리티 메서드입니다.
2. 사용 예시:
   • 힙에 여러 요소를 삽입하고, 최댓값을 추출한 후 힙의 상태를 출력합니다.
   • 힙 속성이 올바르게 유지되는지 확인할 수 있습니다.

 

최소 힙(Min 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(key) {
        this.heap.push(key); // 힙의 끝에 새로운 요소 추가
        this.heapifyUp(this.heap.length - 1); // 힙 속성 유지
    }

    heapifyUp(index) {
        while (index > 0 && this.heap[this.parent(index)] > this.heap[index]) {
            // 부모 노드와 현재 노드의 값을 교환
            [this.heap[this.parent(index)], this.heap[index]] = [this.heap[index], this.heap[this.parent(index)]];
            index = this.parent(index); // 부모 노드로 이동
        }
    }

    extractMin() {
        if (this.heap.length === 0) {
            throw new Error("extractMin from empty heap");
        }
        if (this.heap.length === 1) {
            return this.heap.pop();
        }
        const root = this.heap[0]; // 루트 노드(최소값) 저장
        this.heap[0] = this.heap.pop(); // 마지막 노드를 루트로 이동
        this.heapifyDown(0); // 힙 속성 유지
        return root;
    }

    heapifyDown(index) {
        const size = this.heap.length;
        while (true) {
            let smallest = index;
            const left = this.leftChild(index);
            const right = this.rightChild(index);

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

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

            if (smallest !== index) {
                // 현재 노드와 가장 작은 자식 노드의 값을 교환
                [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
                index = smallest; // 교환된 자식 노드로 이동
            } else {
                break; // 힙 속성이 유지되면 종료
            }
        }
    }

    peekMin() {
        if (this.heap.length === 0) {
            throw new Error("peekMin from empty heap");
        }
        return this.heap[0];
    }

    size() {
        return this.heap.length;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    displayHeap() {
        console.log(this.heap);
    }
}

// 최소 힙 사용 예시
const minHeap = new MinHeap();
const elements = [10, 4, 15, 20, 0, 8];
for (let el of elements) {
    minHeap.insert(el);
}
console.log("Min Heap:", minHeap.heap); // 출력: Min Heap: [0, 4, 8, 20, 10, 15]

console.log("Extract Min:", minHeap.extractMin()); // 출력: Extract Min: 0
console.log("Heap after extracting min:", minHeap.heap); // 출력: Heap after extracting min: [4, 10, 8, 20, 15]

console.log("Peek Min:", minHeap.peekMin()); // 출력: Peek Min: 4

코드 설명

1. MinHeap 클래스:
   • constructor 메서드:
     • this.heap는 힙을 저장하는 배열입니다.
   • parent, leftChild, rightChild 메서드:
     • 주어진 인덱스의 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드의 인덱스를 계산합니다.
   • insert 메서드:
     • 새로운 키를 힙의 끝에 추가한 후, heapifyUp 메서드를 호출하여 힙 속성을 유지합니다.
   • heapifyUp 메서드:
     • 새로운 요소를 힙의 위로 이동시켜 힙 속성을 유지합니다.
     • 부모 노드의 값이 현재 노드의 값보다 크면 두 값을 교환하고, 부모 노드로 이동하여 반복합니다.
   • extractMin 메서드:
     • 힙의 루트 노드(최솟값)를 추출합니다.
     • 마지막 노드를 루트로 이동시킨 후, heapifyDown 메서드를 호출하여 힙 속성을 유지합니다.
   • heapifyDown 메서드:
     • 루트 노드에서 시작하여 힙 속성을 유지하기 위해 아래로 이동합니다.
     • 현재 노드의 자식 노드들과 비교하여 가장 작은 값을 가진 노드와 교환합니다.
   • peekMin 메서드:
     • 힙의 루트 노드(최솟값)를 반환합니다.
   • size, isEmpty, displayHeap 메서드:
     • 힙의 크기 확인, 비어있는지 확인, 힙의 현재 상태를 출력하는 유틸리티 메서드입니다.
2. 사용 예시:
   • 힙에 여러 요소를 삽입하고, 최솟값을 추출한 후 힙의 상태를 출력합니다.
   • 힙 속성이 올바르게 유지되는지 확인할 수 있습니다.

 

 

---

 

 

힙(Heap)의 응용 예제

 

우선순위 큐(Priority Queue) 구현

힙은 우선순위 큐의 구현에 이상적인 자료구조입니다.

 

Python으로 우선순위 큐 구현하기

class PriorityQueue:
    def __init__(self):
        self.max_heap = MaxHeap()

    def enqueue(self, item):
        self.max_heap.insert(item)

    def dequeue(self):
        return self.max_heap.extract_max()

    def peek(self):
        return self.max_heap.peek_max()

    def is_empty(self):
        return self.max_heap.is_empty()

    def size(self):
        return self.max_heap.size()

    def display(self):
        self.max_heap.display_heap()

# 우선순위 큐 사용 예시
if __name__ == "__main__":
    pq = PriorityQueue()
    pq.enqueue(10)
    pq.enqueue(5)
    pq.enqueue(15)
    pq.enqueue(20)
    pq.enqueue(0)

    print("Priority Queue:", pq.max_heap.heap)  # 출력: Priority Queue: [20, 10, 15, 5, 0]

    print("Peek:", pq.peek())  # 출력: Peek: 20
    print("Dequeue:", pq.dequeue())  # 출력: Dequeue: 20
    print("Priority Queue after dequeue:", pq.max_heap.heap)  # 출력: Priority Queue after dequeue: [15, 10, 0, 5]

    print("Size:", pq.size())  # 출력: Size: 4
    print("Is Empty:", pq.is_empty())  # 출력: Is Empty: False

코드 설명

1. PriorityQueue 클래스:
   • init 메서드:
     • self.max_heap은 최대 힙을 사용하여 우선순위 큐를 구현합니다.
   • enqueue 메서드:
     • 아이템을 큐에 추가하기 위해 최대 힙에 삽입합니다.
   • dequeue 메서드:
     • 큐에서 우선순위가 가장 높은 아이템을 추출하기 위해 최대 힙에서 최댓값을 추출합니다.
   • peek 메서드:
     • 큐의 우선순위가 가장 높은 아이템을 확인합니다.
   • is_empty, size, display 메서드:
     • 큐의 상태를 확인하고, 현재 힙의 상태를 출력합니다.
2. 사용 예시:
   • 우선순위 큐에 여러 아이템을 삽입하고, 최댓값을 추출한 후 큐의 상태를 출력합니다.
   • 우선순위 큐의 기본 동작을 확인할 수 있습니다.

 

JavaScript으로 우선순위 큐 구현하기

 

class PriorityQueue {
    constructor() {
        this.maxHeap = new MaxHeap();
    }

    enqueue(item) {
        this.maxHeap.insert(item);
    }

    dequeue() {
        return this.maxHeap.extractMax();
    }

    peek() {
        return this.maxHeap.peekMax();
    }

    isEmpty() {
        return this.maxHeap.isEmpty();
    }

    size() {
        return this.maxHeap.size();
    }

    display() {
        this.maxHeap.displayHeap();
    }
}

// 우선순위 큐 사용 예시
const pq = new PriorityQueue();
pq.enqueue(10);
pq.enqueue(5);
pq.enqueue(15);
pq.enqueue(20);
pq.enqueue(0);

console.log("Priority Queue:", pq.maxHeap.heap); // 출력: Priority Queue: [20, 10, 15, 5, 0]

console.log("Peek:", pq.peek()); // 출력: Peek: 20
console.log("Dequeue:", pq.dequeue()); // 출력: Dequeue: 20
console.log("Priority Queue after dequeue:", pq.maxHeap.heap); // 출력: Priority Queue after dequeue: [15, 10, 0, 5]

console.log("Size:", pq.size()); // 출력: Size: 4
console.log("Is Empty:", pq.isEmpty()); // 출력: Is Empty: false

코드 설명

1. PriorityQueue 클래스:
   • constructor 메서드:
     • this.maxHeap은 최대 힙을 사용하여 우선순위 큐를 구현합니다.
   • enqueue 메서드:
     • 아이템을 큐에 추가하기 위해 최대 힙에 삽입합니다.
   • dequeue 메서드:
     • 큐에서 우선순위가 가장 높은 아이템을 추출하기 위해 최대 힙에서 최댓값을 추출합니다.
   • peek 메서드:
     • 큐의 우선순위가 가장 높은 아이템을 확인합니다.
   • isEmpty, size, display 메서드:
     • 큐의 상태를 확인하고, 현재 힙의 상태를 출력합니다.
2. 사용 예시:
   • 우선순위 큐에 여러 아이템을 삽입하고, 최대값을 추출한 후 큐의 상태를 출력합니다.
   • 우선순위 큐의 기본 동작을 확인할 수 있습니다.

 

힙 정렬(Heap Sort) 구현하기

 

힙 정렬은 힙을 활용한 효율적인 정렬 알고리즘으로, 힙의 특성을 이용하여 데이터를 정렬합니다. 힙 정렬은 O(n log n)의 시간 복잡도를 가지며, 공간 복잡도는 O(1)입니다.

 

Python으로 힙 정렬 구현하기

def heap_sort(arr):
    n = len(arr)
    max_heap = MaxHeap()
    for element in arr:
        max_heap.insert(element)

    sorted_arr = []
    while not max_heap.is_empty():
        sorted_arr.append(max_heap.extract_max())

    sorted_arr.reverse()  # 오름차순 정렬을 위해 반전
    return sorted_arr

# 힙 정렬 사용 예시
if __name__ == "__main__":
    array = [12, 11, 13, 5, 6, 7]
    sorted_array = heap_sort(array)
    print("Sorted array:", sorted_array)  # 출력: Sorted array: [5, 6, 7, 11, 12, 13]

코드 설명

1. heap_sort 함수:
   • 매개변수: 정렬할 배열 arr.
   • 동작:
     1. 배열의 모든 요소를 최대 힙에 삽입합니다.
     2. 힙에서 최대값을 추출하여 sorted_arr 리스트에 추가합니다.
     3. 힙에서 모든 요소를 추출한 후, sorted_arr를 반전하여 오름차순으로 정렬된 배열을 반환합니다.
   • 시간 복잡도: O(n log n).
   • 공간 복잡도: O(n) (추가적인 리스트 사용).
2. 사용 예시:
   • 힙 정렬을 사용하여 배열 [12, 11, 13, 5, 6, 7]을 오름차순으로 정렬합니다.
   • 결과는 [5, 6, 7, 11, 12, 13]입니다.

 

JavaScript으로 힙 정렬 구현하기

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(key) {
        this.heap.push(key); // 힙의 끝에 새로운 요소 추가
        this.heapifyUp(this.heap.length - 1); // 힙 속성 유지
    }

    heapifyUp(index) {
        while (index > 0 && this.heap[this.parent(index)] > this.heap[index]) {
            // 부모 노드와 현재 노드의 값을 교환
            [this.heap[this.parent(index)], this.heap[index]] = [this.heap[index], this.heap[this.parent(index)]];
            index = this.parent(index); // 부모 노드로 이동
        }
    }

    extractMin() {
        if (this.heap.length === 0) {
            throw new Error("extractMin from empty heap");
        }
        if (this.heap.length === 1) {
            return this.heap.pop();
        }
        const root = this.heap[0]; // 루트 노드(최소값) 저장
        this.heap[0] = this.heap.pop(); // 마지막 노드를 루트로 이동
        this.heapifyDown(0); // 힙 속성 유지
        return root;
    }

    heapifyDown(index) {
        const size = this.heap.length;
        while (true) {
            let smallest = index;
            const left = this.leftChild(index);
            const right = this.rightChild(index);

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

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

            if (smallest !== index) {
                // 현재 노드와 가장 작은 자식 노드의 값을 교환
                [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
                index = smallest; // 교환된 자식 노드로 이동
            } else {
                break; // 힙 속성이 유지되면 종료
            }
        }
    }

    size() {
        return this.heap.length;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    displayHeap() {
        console.log(this.heap);
    }
}

function heapSort(arr) {
    const minHeap = new MinHeap();
    for (let el of arr) {
        minHeap.insert(el); // 모든 요소를 최소 힙에 삽입
    }

    const sortedArr = [];
    while (!minHeap.isEmpty()) {
        sortedArr.push(minHeap.extractMin()); // 최소값을 추출하여 정렬된 배열에 추가
    }

    return sortedArr;
}

// 힙 정렬 사용 예시
const array = [12, 11, 13, 5, 6, 7];
const sortedArray = heapSort(array);
console.log("Sorted array:", sortedArray); // 출력: Sorted array: [5, 6, 7, 11, 12, 13]

코드 설명

1. MinHeap 클래스:
   • 최소 힙의 구현으로, 힙 속성을 유지하기 위해 heapifyUp과 heapifyDown 메서드를 사용합니다.
   • insert 메서드: 새로운 키를 힙에 삽입하고, 힙 속성을 유지합니다.
   • extractMin 메서드: 힙의 루트 노드(최솟값)를 추출하고, 힙 속성을 유지합니다.
   • heapifyUp, heapifyDown 메서드: 힙 속성을 유지하기 위해 요소를 위 또는 아래로 이동시킵니다.
   • size, isEmpty, displayHeap 메서드: 힙의 크기 확인, 비어있는지 확인, 힙의 현재 상태를 출력하는 유틸리티 메서드입니다.
2. heapSort 함수:
   • 매개변수: 정렬할 배열 arr.
   • 동작:
     1. 모든 요소를 최소 힙에 삽입합니다.
     2. 힙에서 최솟값을 추출하여 sortedArr 리스트에 추가합니다.
     3. 힙에서 모든 요소를 추출한 후, sortedArr는 오름차순으로 정렬된 배열이 됩니다.
   • 시간 복잡도: O(n log n).
   • 공간 복잡도: O(n) (추가적인 배열 사용).
3. 사용 예시:
   • 힙 정렬을 사용하여 배열 [12, 11, 13, 5, 6, 7]을 오름차순으로 정렬합니다.
   • 결과는 [5, 6, 7, 11, 12, 13]입니다.

 

---

 

힙(Heap)의 장단점

 

힙의 장점

• 빠른 우선순위 관리: 힙은 삽입과 삭제 연산이 O(log n) 시간 복잡도를 가지며, 우선순위 큐의 구현에 이상적입니다.
• 효율적인 정렬: 힙 정렬은 O(n log n) 시간 복잡도를 가지며, 안정적인 성능을 제공합니다.
• 유연한 자료구조: 최대 힙과 최소 힙을 통해 다양한 우선순위 기반 작업을 지원합니다.

 

힙의 단점

• 구조 제한: 힙은 완전 이진트리의 형태를 가져야 하므로, 일반적인 트리나 그래프에 비해 유연성이 떨어집니다.
• 메모리 사용: 힙을 배열로 구현할 경우, 배열의 크기를 미리 정해야 하거나 동적으로 조절해야 하므로 추가적인 메모리 관리가 필요합니다.
• 탐색 제한: 힙은 최댓값 또는 최솟값을 빠르게 찾을 수 있지만, 임의의 요소를 찾는 데는 비효율적입니다 (O(n) 시간 복잡도).

 

 

 

 

 

힙(Heap)은 우선순위 관리와 효율적인 정렬을 가능하게 하는 강력한 자료구조입니다. 우선순위 큐 구현, 힙 정렬, 그래프 알고리즘 등 다양한 문제를 효율적으로 해결하는 데 필수적인 도구입니다. 다음 포스트에서는 트리(Tree) 자료구조의 확장인 AVL 트리와 레드-블랙 트리에 대해 심도 있게 알아보겠습니다.

 

 

 

 

 

참고 자료

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

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

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

Heap Data Structure - GeeksforGeeks

 

https://docs.python.org/ko/3/library/heapq.html

heapq — Heap queue algorithm