1. Heap이란?

: 우선순위 큐에 의해 만들어진 자료구조

• 우선순위 큐
  우선순위의 개념을 큐에 도입하여 우선순위가 넢은 데이터가 먼저 나가는 특성을 가짐
  주로 작업 스케줄링, 시뮬레이션 시스템에 쓰임
  • 배열, 연결리스트, 힙으로 구현이 가능 (힙이 가장 효율적인 방법 🎯)

• 완전 이진 트리의 일종 (최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조)
• 이진 탐색 트리와 달리 중복된 값도 허용

2. Heap의 종류

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

⚒️ 힙의 구현 (최대 힙 기준)

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

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

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

부모 index = (자식 index) / 2

1) 힙의 삽입

• 힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 삽입
• 새로운 노드를 부모 노드들과 교환하면 자리잡음

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

2) 힙의 삭제

• 최대값(루트노드)를 삭제하면 빈 루트노드에 마지막 노드를 가져옴
• 마지막 노드와 루트노드의 왼쪽 노드와 오른쪽 노드를 비교하여 재구성

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