힙 트리

1. 개요

2. 정의

3. 데이터 처리

3.1. 데이터 삽입

1. 가장 끝의 자리에 노드를 삽입한다.
2. 그 노드와 부모 노드를 서로 비교한다.
3. 규칙에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다. (부모노드는 삽입된 위치의 인덱스 번호에서 /2를 하면 쉽게 구할 수 있다.)
4. 규칙에 맞을 때까지 3번 과정을 반복한다.

3.2. 데이터 삭제

1. 루트 노드를 제거한다.
2. 루트 자리에 가장 마지막 노드를 삽입한다.[3]
3. 올라간 노드와 그의 자식 노드(들)와 비교한다.
4. 조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다.

• 최대 힙
1. 부모보다 더 큰 자식이 없으면 교환하지 않고 끝낸다.
2. 부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환하면 된다.
3. 부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환한다.

• 최소 힙
1. 부모보다 더 작은 자식이 없으면 교환하지 않고 끝낸다.
2. 부모보다 더 작은 자식이 하나만 있으면 그 자식하고 교환하면 된다.
3. 부모보다 더 작은 자식이 둘 있으면 자식들 중 작은 값과 교환한다.

4. 표현

5. 응용 분야

6. 코드

6.1. C++

• 삽입

#!syntax cpp
void creheap(int *arr2, int key, int input) {
  arr2[key] = input;
  while (key > 1) {
    if (arr2[key] < arr2[key / 2]) {
      swap(arr2[key], arr2[key / 2]);
      key /= 2;
    }
    else break;
  }
}

• 삭제
  루트 노드 삭제 후 힙의 마지막 데이터를 가져온 상태를 가정한다.

#!syntax cpp
void delheap(int *arr3, int key, int heap_size) {
  int tmp, nextkey;
  while (heap_size >= key * 2) {
    if (key * 2 + 1 > heap_size && arr3[key * 2] < arr3[key]) {
      swap(arr3[key * 2], arr3[key]);
      key = key * 2;
    }
    else if (key * 2 + 1 > heap_size) break;
    else {
      if (arr3[key * 2] < arr3[key * 2 + 1]) {
        tmp = arr3[key * 2];
        nextkey = key * 2;
      }
      else {
        tmp = arr3[key * 2 + 1];
        nextkey = key * 2 + 1;
      }
      if (tmp < arr3[key]) {
        swap(arr3[key], arr3[nextkey]);
        key=nextkey;
      }
      else break;
    }
  }
}