힙 (Heap)

1. 힙 (Heap)

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree)
  • 완전 이진 트리 : 노드를 삽일할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

힙 사용 이유

• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
• 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)
• 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용

 

2. 힙 (Heap) 구조

• 힙은 최대값을 구하기 위한 구조 (최대힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소힙, Min Heap) 로 분류
• 힙은 다음과 같은 조건을 가지고 있는 자료구조임
  • 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대힙의 경우)
  • 최소힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같다.
  • 완전 이진 트리 형태를 가짐

3. 힙과 이진 탐색 트리의 공통점과 차이점

공통점

• 이진 트리임

차이점

• 힙은 각 노드의 값이 자식 노드보다 크거나 같음 (최대힙의 경우)
• 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고 그 다음 부모 노드 그 다음 오른쪽 자식 노드 값이 가장 큼
• 힙은 이진 탐색 트리의 조건이 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
• 힙의 왼쪽 밑 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음

이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해

 

출처 : https://fastcampus.co.kr/courses/210773/clips/

 

4. 힙 (Heap) 구현

• 배열 이용해서 데이터를 힙 구조에 삽입, 삭제
• root 노드 인덱스 번호를 1로 지정하면 수월함
  • 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 / 2
  • 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
  • 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1

public class Heap {
    private ArrayList<Integer> heap;
    
    public init() {
    	heap = new ArrayList<Integer>();
        heap.add(0); // 0번째 인덱스 사용 안함
    }
    
    public Boolean moveUp(Integer index) {
    	if (index <= 1) {
            return false;
        }
        Integer parentIndex = index / 2;
        if (heap.get(index) > heap.get(parentIndex)) {
            return true;
        } else {
            return false;
        }
    }
    
    public Boolean insert(Integer data) {
    	if (heap.size() == 0) {
            init();
            return true;
        }
        
        heap.add(data);
        
        Integer index = heap.size() - 1;
        while (this.moveUp(index)) {
            Integer parentIndex = index / 2;
            Integer parentData = heap.get(parentIndex); // 부모 노드의 값
            heap.set(parentIndex, data);
            heap.set(index, parentData);
            index = parentIndex;
        }
        return true;
    }
    
    public Boolean moveDown(Integer index) {
    	Integer leftChildIndex = index * 2;
        Integer rightChildIndex = index * 2 + 1;
        
        if (leftChildIndex >= heap.size()) { // 1. 왼쪽 자식 노드도 없을 때
            return false;
        } else if (rightChildIndex >= heap.size()) {  // 2. 오른쪽 자식 노드만 없을 때
            if (heap.get(index) < heap.get(leftChildIndex)) {
            	return true;
            } else {
            	return false;
            }
        } else { // 3. 왼쪽, 오른쪽 자식 노드 모두 있을 때
            if (heap.get(leftChildIndex) > heap.get(rightChildIndex)) {
                if (heap.get(index) < heap.get(leftChildIndex)) {
                    return true;
                } else {
                    return false;
                }
            } else {
            	if (heap.get(index) < heap.get(rightChildIndex)) {
                    return true;
                } else {
                    return false;
                }
            }
        }
    }
    
    public Integer pop() {
    	if (heap.size() <= 1) {
        	return null;
        }
        
        Integer popData = heap.get(1);
        heap.set(1, heap.get(heap.size() - 1);
        heap.remove(heap.size() - 1);
        
        Integer index = 1;
        
        while (this.moveDown(index)) {
            Integer leftChildIndex = index * 2;
            Integer rightChildIndex = index * 2 + 1;
            
            if (rightChildIndex >= heap.size()) { // 2. 오른쪽 자식 노드만 없을 때
            	if (heap.get(index) < heap.get(leftChildIndex)) {
                    Integer leftChildData = heap.get(leftChildIndex);
                    heap.set(leftChildIndex, heap.get(index));
                    heap.set(index, leftChildData);
                }
            } else { // 3. 왼쪽, 오른쪽 자식 노드 모두 있을 때
            	if (heap.get(leftChildIndex) > heap.get(rightChildIndex)) {
                    if (heap.get(index) < heap.get(leftChildIndex)) {
                        Integer leftChildData = heap.get(leftChildIndex);
                        heap.set(leftChildIndex, heap.get(index));
                        heap.set(index, leftChildData);
                    }
            	} else {
                    if (heap.get(index) < heap.get(rightChildIndex)) {
                        Integer rightChildData = heap.get(rightChildIndex);
                        heap.set(rightChildIndex, heap.get(index));
                        heap.set(index, rightChildData);
                    }
                }
            }
        }
        return popData;
    }
    
	public 
}

 

5. 힙 (Heap) 시간 복잡도

• O(logn)