힙(Heap)

💡 Goal

- 힙(Heap)에 대한 이해
- 배열을 이용한 힙(Heap) 구현
- 힙(Heap)의 삽입과 삭제 구현

힙은 우선순위 큐를 위해 만들어진 자료구조이다.

우선순위 큐에 대해서 간략히 먼저 알아보자면,

 

우선순위 큐 : 우선순위의 개념을 큐에 도입한 자료 구조이다.

- 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.

- 우선순위 큐를 힙으로 구현하면 삽입/삭제의 시간복잡도가 O(logN)으로 배열, 연결리스트로 구현하는 것보다 훨씬 효율적이다. 

- 우선순위 큐의 이용 사례

• 시뮬레이션 시스템
• 네트워크 트래픽 제어
• 작업 스케줄링

우선순위큐  배열, 연결리스트, 힙 구현 시간복잡도

힙(Heap)

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조
• 반정렬 상태
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나(작거나) 한 이진트리를 말한다.
• 힙 트리는 중복된 값을 허용(이진 탐색 트리는 중복값 허용x) 

힙(Heap)의 종류

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

 

 

힙(Heap)의 구현

- 힙을 저장하는 표준적인 자료구조는 배열이다. 

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

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

ex) 루트노드(1)의 오른쪽 노드의 번호는 항상 3이다.

 

- 힙에서 부모 노드와 자식 노드의 관계

• 왼쪽 자식 인덱스 = (부모 인덱스)*2
• 오른쪽 자식 인덱스 = (부모 인덱스)*2+1
• 부모 인덱스 = (자식 인덱스)/2

■ heap 조정 규칙

 

- index 위치의 값이 heap의 성질을 만족하지 않을 때, 재조정 절차

- heap의 끝 값을 루트로 이동한 후, heap의 성질이 만족되도록 조정하는 절차

- heap은 "완전이진트리"이므로, 임의의 노드의 자식의 수는 두 자식이 다 있거나, 왼쪽 자식만 있거나, 자식이 없거나 이다. 

 

1. 두 자식이 다 있는 경우

왼쪽 자식 인덱스 < 오른쪽 자식 인덱스 <= 마지막 인덱스

 

2. 왼쪽 자식만 있는 경우

왼쪽 자식 인덱스 <= 마지막 인덱스 < 오른쪽 자식 인덱스

 

3. 자식이 없는 경우

마지막 인덱스 < 왼쪽 자식 인덱스 < 오른쪽 자식 인덱스

 

// 최소힙 heapify 구현
heapify(int[] a, int index) { // index 위치의 노드가 heap 성질을 만족하도록 조정
	leftChildIndex = 2 * index;
    rightChildIndex = 2 * index+1;
    endIndex = a.length - 1;
  
    // 자식이 둘 다 있다면, smallIndex를 구한다.
    if(rightChildIndex <= endIndex) 
    	smallIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex
    
    // 왼쪽 자식만 있다면, 왼쪽 자식이 smallIndex
    else if(leftChildIndex <= endIndex) 
    	smallIndex = left ChildIndex
     
    // 자식이 없다면 리턴
    else return;
    
    // smallIndex 값 보다 index 값이 더 크면 swap
    if(a[index] > a[smallIndex]) {
    	swap(a, index, smallIndex)
        heapify(a, smallIndex) // 다은 단계 재귀호출
    }
}
    

 

 

힙(Heap)의 삽입

1. 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.

2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다. 

 

최대힙(max heap)에 새로운 요소 8을 삽입해봅시당

 

최대힙 삽입 구현(Java)

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;
        }
        
    }
}

 

힙(heap)의 삭제

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

• 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다 

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

3. 힙을 재구성한다.

 

아래의 최대 힙(max heap)에서 최댓값을 삭제해보자.

 

 

최대힙  삭제 구현(Java)

int delete_max_heap() {
	if(heaSize == 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;
 }