---

힙(Heap)

---

1. 우선순위 큐

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

• 배열, 연결리스트, 힙으로 구현할 수 있다.(힙으로 구현이 가장 효율적이다.)

• 힙 -> 삽입 : O(logn), 삭제 : O(logn)

2. 힙(Heap)

• 완전 이진트리의 일종이다.(여러 값 중 최대값, 최소값을 빠르게 찾아내도록 만들어진 자료구조)

• 힙 트리는 중복된 값을 허용한다.(이진 탐색 트리는 중복값을 허용하지 않는다.)

3. 힙 종류

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

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

4. 구현

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

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

• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.(루트 노드(1)의 오른쪽 노드 번호는 항상 3)

• 부모 노드와 자식 노드 관계
  -> 왼쪽 자식 index = (부모 index) 2
  -> 오른쪽 자식 index = (부모 index) 2 + 1
  -> 부모 index = (자식 index) / 2

5. 힙의 삽입

• 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입하고 부모 노드들과 교환한다.

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

6. 힙의 삭제

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

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

• 힙을 재구성한다.

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