[자료구조] 힙(heap)

1. 힙이란?

힙이란 어떤 구조냐에 따라 위에서부터 아래로 자식으로 내려갈수록 값이 커지거나 자식으로 내려갈수록 값이 작아지는 것입니다. 즉, 높이에 따라 정렬된다고 볼 수 있습니다.

힙이 최소힙일때는 루트의 값이 가장 작고, 힙이 최대힙을때는 루트의 값이 가장 큽니다.

그리고 힙의 특징 중 하나는 완전이진트리라는 것입니다. 즉, 높이에 따른 노드의 값이 모두 채워져야 자식노드로 내려갈 수 있다는 것입니다.

 

최소힙은 아래 그림으로 확인하실 수 있습니다. 최대힙은 반대로 가장 큰 값이 루트에 있습니다.

 

최소힙 출처: 얄코의 가장 쉬운 자료구조와 알고리즘

다만 주의해야할 것은 같은 높이의 모든 노드값이 한단계 위나 아래의 모든 노드보다 크거나 작지는 않다는 것입니다.

예를 들면 부모노드와 같은 높이의 다른 노드를 삼촌노드라고 했을 때 자식노드가 삼촌노드보다는 무조건 크거나 작지는 않다는 것입니다. 그림을 확인해보면 아래와 같습니다.

 

힙을 파이썬과 자바 코드로 확인해보겠습니다.

 

파이썬

class MinHeap:
    def __init__(self):
        self.heap = []
	
    ## 추가된 노드가 직계 조상들과 비교하여 자기 자리를 찾아가는 메서드
    def heapify_up(self, index):
        parent = (index - 1) // 2
        if (index > 0 and
            self.heap[index] < self.heap[parent]):
            self.heap[index], self.heap[parent] = \
                self.heap[parent], self.heap[index]
            self.heapify_up(parent)
	
    ## 노드를 아래로 밀어내리는 메서드
    def heapify_down(self, index):
        smallest = index
        left = 2 * index + 1
        right = 2 * index + 2
        size = len(self.heap)

        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]
            self.heapify_down(smallest)
	
    ## 트리의 중간부터 값을 밀어내려 정렬시킴으로써 힙 구조를 완성해주는 메서드
    def build_heap(self, arr):
        self.heap = arr[:]
        for i in range((len(self.heap) // 2) - 1, -1, -1):
            self.heapify_down(i)

    def insert(self, val):
        self.heap.append(val)
        self.heapify_up(len(self.heap) - 1)
	
    ## 루트 노드를 제거하고 반환하는 메서드(최소힙 기준)
    def remove_min(self):
        if not self.heap:
            return None
        min_val = self.heap[0]
        last = self.heap.pop()
        if self.heap:
            self.heap[0] = last
            self.heapify_down(0)
        return min_val
	
    ## 루트노드를 제거하지 않고 반환하는 메서드
    def get_min(self):
        if not self.heap:
            return None
        return self.heap[0]


heap = MinHeap()
heap.build_heap([5, 3, 8, 4, 1, 2])
print(heap.heap)  
# [1, 3, 2, 4, 5, 8]

heap.insert(6)
print(heap.heap)  
# [1, 3, 2, 4, 5, 8, 6]

print(heap.get_min())     # 1
print(heap.remove_min())  # 1
print(heap.heap)          
# [2, 3, 6, 4, 5, 8]

 

자바

import java.util.ArrayList;
import java.util.List;

public class MinHeap {
    private List<Integer> heap;

    public MinHeap() {
        heap = new ArrayList<>();
    }
    
    private void heapifyUp(int index) {
        int parent = (index - 1) / 2;
        if (index > 0 &&
            heap.get(index) < heap.get(parent)) {
            swap(index, parent);
            heapifyUp(parent);
        }
    }
    
    private void swap(int i, int j) {
        int tmp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, tmp);
    }

    private void heapifyDown(int index) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int size = heap.size();

        if (left < size &&
            heap.get(left) < heap.get(smallest)) {
            smallest = left;
        }
        if (right < size &&
            heap.get(right) < heap.get(smallest)) {
            smallest = right;
        }

        if (smallest != index) {
            swap(index, smallest);
            heapifyDown(smallest);
        }
    }
        
    public void buildHeap(List<Integer> arr) {
        heap = new ArrayList<>(arr);
        for (int i = (heap.size() / 2) - 1; i >= 0; i--) {
            heapifyDown(i);
        }
    }

    public void insert(int val) {
        heap.add(val);
        heapifyUp(heap.size() - 1);
    }

    public Integer removeMin() {
        if (heap.isEmpty()) return null;
        int min = heap.get(0);
        int last = heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) {
            heap.set(0, last);
            heapifyDown(0);
        }
        return min;
    }

    public Integer getMin() {
        if (heap.isEmpty()) return null;
        return heap.get(0);
    }

    public static void main(String[] args) {
        MinHeap heap = new MinHeap();
        List<Integer> arr = List.of(5, 3, 8, 4, 1, 2);
        heap.buildHeap(arr);
        System.out.println(heap.heap);
        // [1, 3, 2, 4, 5, 8]

        heap.insert(6);
        System.out.println(heap.heap); 
        // [1, 3, 2, 4, 5, 8, 6]

        System.out.println(heap.getMin());     // 1
        System.out.println(heap.removeMin());  // 1
        System.out.println(heap.heap);         
        // [2, 3, 6, 4, 5, 8]
    }
}

 

힙은 우선순위 큐로 많이 사용됩니다. 위 코드에서 루트 노드를 빼서 반환하기 때문에 힙에 값을 넣은 순서와 상관없이 작은 값부터 또는 큰 값부터 큐에서 꺼낼 수 있기 때문입니다.

 

2. 최소힙 모듈

파이썬에서는 최소힙이 내장 라이브러리로 구현되어있습니다. 최대힙은 없기 때문에 최소힙을 통해서 따로 만들어야합니다.

최소 힙 모듈 사용방법은 아래와 같습니다.

 

import heapq # 최소힙 모듈

data_list = []
data_list2 = [100,50,20]

heapq.heappush(data_list,50)
heapq.heappush(data_list,20)
heapq.heappush(data_list,30)
print(data_list) #[20, 50, 30] -> 최소힙 정렬

heapq.heapify(data_list2) # 힙으로 변환
print(data_list2) # [20, 50, 100]

# 최소 힙 출력 -> 작은 값부터 먼저 출력
print(heapq.heappop(data_list)) # 20
print(heapq.heappop(data_list)) # 30
print(heapq.heappop(data_list)) # 50

# 최소 힙 출력 -> 작은 값부터 먼저 출력
print(heapq.heappop(data_list2)) # 20
print(heapq.heappop(data_list2)) # 50
print(heapq.heappop(data_list2)) # 100