[자료구조] 힙(Heap)이란?

 

 

힙(Heap)이란? 

• 완전 이진 트리로 이루어진 자료구조! (자식이 두개이며, leaf는 왼쪽부터 채워진다)
• 느슨한 정렬 상태를 유지한다.
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
  • 최대값(최소값)을 빠르게 찾을 수 있도록 한다.

 

종류

최대힙과 최소힙으로 구분할 수 있다.

• 최대힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 (부모 키 값 >= 자식 키 값)
• 최소힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 (부모 키 값 <= 자식 키 값)

 

 

---

 

 

힙(Heap) 구현은 어떻게 할까?

• 일반적으로 배열을 사용하여 힙(heap)을 구현한다. (구현의 용이를 위해 1번방부터 채워준다.)
• 완전 이진 트리의 규칙을 따라 자식 노드를 왼쪽부터 채워줄 경우,
  • n번째 노드의 자식들은 2n, 2n+1번째에 채워지게 된다.
  • n번째 노드의 부모는 n / 2 번째에 위치한다.
• 아래 최소힙을 통해 예를 들어보자.

 

https://reakwon.tistory.com/42

 

index	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
key	-	1	2	3	4	5	6	7

 

 

 

 

삽입 (Insert)

삽입이 될 새로운 키를 newKey라고 하자. 

1. 마지막 위치에 newKey를 채워준다.
2. newKey < 부모 Key 일 경우, 부모와 key 값을 교체한다.
3. Root까지 2번 작업을 반복한다.

void insert(int newKey) {
	heap[++heapSize] = newKey;
    
    for (int i = heapSize; i > 1; i /= 2) {
    	if (heap[i / 2] > heap[i]) {
        	swap(i / 2, i);
        }
        else {
        	break;
        }
    }
}

 

 

 

삭제 (Delete)

 Heap에서의 삭제는 Root 삭제를 의미한다.

1. Root 삭제한다.
2. 가장 마지막 Key를 Root로 옮겨준다.
3. Key > 자식 Key 일 경우, 자식 중 더 작은 자식과 교체한다.
4. 3번 작업을 반복하여 더 이상 큰 자식이 없을 경우 작업을 마친다.

int delete() {
	if (heapSize == 0) return 0;
    
    int rootKey = heap[1];
    heap[1] = heap[heapSize--];
    
    for (int i = 1; 2 * i <= heapSize) {
    	int leftChild = 2 * i;
    	int rightChild = 2 * i + 1;
    
    	if (heap[i] < heap[leftChild] && heap[i] < heap[rightChild]) break;
        
        if (heap[leftChild] < heap[rightChild]) {
        	swap(i, rightChild);
            i = rightChild;
        } 
        else {
        	swap(i, leftChild);
            i = leftChild;
        }
    }
    
    return rootKey;
}

 

 

 

 

 

Reference

• https://reakwon.tistory.com/42
• https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html