[자료구조] 힙(Heap)

힙(Heap)

---

힙(Heap)

완전 이진 트리의 일종이며 여러 값 중 최대 값과 최소 값을 빠르게 찾아내도록 만들어진 자료구조이다. 이진 탐색 트리가 중복 값을 허용하지 않는 것과 달리 힙 트리는 중복된 값을 허용한다.

 

---

힙(Heap) 종류

[최대 힙(Max heap)]

부모 노드이 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다.

 

[최소 힙(min heap)]

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다.

 

---

구현

힙은 배열을 사용하여 구현하게 된다.

구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용하지 않는다.

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

 

 

부모 노드와 자식 노드의 관계

왼쪽 자식 index = (부모 index) * 2

오른쪽 자식 index = (부모 index) * 2 + 1

부모 index = (자식 index) / 2

 

힙의 삽입

 

 

void insert_max_heap(int x) {
    
    maxHeap[++heapSize] = x; 
    // 힙 크기를 하나 증가하고, 마지막 노드에 x를 넣음
    
    for( int i = heapSize; i > 1; i /= 2) {
        
        // 마지막 노드가 자신의 부모 노드보다 크면 swap
        if(maxHeap[i/2] < maxHeap[i]) {
            swap(i/2, i);
        } else {
            break;
        }
        
    }
}

 

힙의 삭제

 

1. 최대 힙 에서 최대 값은 루트 노드이므로 루트 노드가 삭제된다.

(최대 힙에서 삭제 연산은 최대 값 요소를 삭제하는 것을 의미한다.)

2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.

3. 힙을 재 구성한다. 

 

int delete_max_heap() {
    
    if(heapSize == 0) // 배열이 비어있으면 리턴
        return 0;
    
    int item = maxHeap[1]; // 루트 노드의 값을 저장
    maxHeap[1] = maxHeap[heapSize]; // 마지막 노드 값을 루트로 이동
    maxHeap[heapSize--] = 0; // 힙 크기를 하나 줄이고 마지막 노드 0 초기화
    
    for(int i = 1; i*2 <= heapSize;) {
        
        // 마지막 노드가 왼쪽 노드와 오른쪽 노드보다 크면 끝
        if(maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1]) {
            break;
        }
        
        // 왼쪽 노드가 더 큰 경우, swap
        else if (maxHeap[i*2] > maxHeap[i*2+1]) {
            swap(i, i*2);
            i = i*2;
        }
        
        // 오른쪽 노드가 더 큰 경우
        else {
            swap(i, i*2+1);
            i = i*2+1;
        }
    }
    
    return item;
    
}

 

---

Reference

 

 

[자료구조] 힙(heap)이란 - Heee's Development Blog