[자료구조] Heap

힙 ( Heap )

 

---

1) 개념

무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 '완전 이진 트리'를 기본으로 한 자료구조
• A가 B의 부모노드면, A의 키 값이 B의 키 값 사이에 대소 관계가 성립 = 힙(Heap)의 속성
• 부모 노드가 최댓값일 경우 '최대 힙', 최솟값일 경우 '최소 힙'
• 대소관계는 오로지 부모와 자식간에만 성립, 형제 사이끼리는 정해지지 않음
  • 원소의 정렬이 끝까지 이뤄지지 않고 최대, 최소를 구하는 것만 확실
• 이런 특징을 이용해 '우선순위 큐'와 같은 추상적 자료형을 구현
• 시간 복잡도
  • 최소/최대 원소에 접근하는 동작은 O(1)
  • 삽입은 O(log n)
  • 제거는 최소/최대 원소에 대해서만 가능

---

2) 이진 힙

• 내부노드에 키와 요소를 저장한 이진 트리
• i번째 노드의 왼쪽 자식노드의 위치는 (2 * i)
• i번째 노드의 오른쪽 자식노드의 위치는 (2 * i + 1)
• i번째 노드의 부모노드의 위치는 (i / 2)

---

3 - 1) 연산 - 삽입

1. 완전 이진 트리를 유지해야함
2. 새 요소는 힙의 마지막 노드에 삽입
3. 새 노드가 기존 노드보다 크다면 값을 비교하고 교환
4. 자식 노드와도 마찬가지로 비교

void insert_max_heap(int x)
{
    maxHeap[++heapSize] = x;

    for(int i = heapSize; i > 1; i /= 2)
    {
        // 부모노드와 자기 자신비교해 부모가 작으면 swap
        if(maxHeap[i/2] < maxHeap[i])
        {
            swap(i/2, i);
        }
        else
            break;
    }
}

---

3 - 2) 연산 - 삭제

1. 가장 큰(작은) 원소, 루트 노드만 삭제 가능 => 다른 원소에 직접 접근이 불가능 하기 때문
2. 루트 노드와 마지막 노드를 교환후 마지막 노드를 삭제
3. 루트 노드와 두 자식 노드를 비교 후 더 큰 노드와 서로 교환, 이를 재귀적으로 반복

int delete_max_heap()
{
    if(heapSize == 0)
        return 0;

    int node = maxHeap[1];
    maxHeap[1] = maxHeap[heapSize];
    maxHeap[heapSize--] = 0;

    for(int i = 1; i * 2 <= heapSize;)
    {
        // 마지막 노드가 왼쪽, 오른쪽 자식 노드보다 크면 끝
        if(maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1])
            break;
        // 왼쪽이 큰 경우
        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;
        }
    }
}

---

3 - 3) 연산 - 초기화 

- 불변성을 유지해야 하기 때문에 초기화가 어렵고 효율적이지 않으나 비어있는 힙에 하나씩 원소를 삽입하는 것
- 힙 생성 알고리즘을 사용
        -> 전체 트리의 아래쪽 서브 트리부터 힙 불변성을 만족하도록 힙을 업데이트하는 방식
        -> C++ 표준은 배열 또는 벡터의 반복자를 인자로 받아 힙을 구성하는 std::make_heap() 함수를 제공