힙(Heap), 힙화(Heapify), 최댓값, 최솟값 구하기, 구현

 

 

●힙(Heap)

- 최댓값, 최솟값을 빠르게 검색할 수 있는 자료구조

- 완전이진트리(Complete Binary Tree) 형태로 구성

- Max Heap, Min Heap으로 구성

 

- Max Heap(최대 힙)

부모노드 >= 자식노드

=> 루트에 최댓값이 들어있다.

 

- Min Heap(최소 힙)

부모노드 <= 자식노드

=> 루트에 최솟값이 들어있다.

 

-힙 트리에서는 이진탐색트리와는 다르게 중복된 값을 허용한다.

 

-힙화(Heapify)

무작위로 데이터가 들어간 배열 구조를 힙 구조에 맞게 변경하는 것

 

 

이런 트리구조가 있다고 해보자.

 

                                   3

                       2                        4

                1            5          6

 

 

먼저 자식노드가 있는 노드들을 중심으로 생각한다.

1, 5, 6은 자식 노드가 없기 때문에 일단 제쳐놓는다.

 

자식중에 더 큰 노드의 값을 찾는다.

부모와 자식을 비교한 다음 자식이 더 크면 둘을 스왑해준다.

2의 자식을 보면 1과 5중에서 5가 더 크다.

그리고 2와 5를 비교해보면 자식인 5가 더 크기 때문에 둘을 스왑한다.

 

4의 자식을 보면 6과 4중에서 자식인 6이 더 크기 때문에 둘을 스왑한다.

그러면 트리 구조가

                                   3

                       5                        6

                1            2          4

 

이 될 것이다.

 

 

이 과정을 한번 더 한다.

5와 6을 비교하면 6이 더 크다.

그리고 6과 3을 비교하면 자식인 6이 더 크기 때문에 스왑한다.

 

그래서

                                    6

                       5                        3

                1            2          4

 

이런 트리구조가 될 것이다.

 

그런데 여기서 3과 6을 바꿔버리니 또 3이 4보다 작게 되어서 3과 4를 바꿔준다.

 

 

최종적으로

 

                                    6

                       5                        4

                1            2          3

 

이러한 트리구조가 완성된다.

 

이 과정에서 알 수 있는 것은

교환된 값을 자식과 비교해서 부모랑 바꿔주는 작업을 계속적으로 해줘야 하기 때문에

재귀호출이 필요하다는 것이다.

 

- 최댓값을 찾을 때 루트의 값만 뽑으면 된다.

=> 배열을 힙화 시키는 것은 최댓값이나 최솟값을 빠르게 찾기 위함이다.

 

 

---

 

 

●힙화 코드로 구현

 

#define SIZE 10;

typedef struct HEAP {
  int* arr;
  int size;
  int capacity;
} HEAP;

int main() {
  int a[SIZE] = {3, 7, 2, 9, 1, 6, 4, 10, 5, 8};
  HEAP heap;
  heapify(&heap, a, 10);
  return 0;
}

void heapify(heap* p, int* a, int size) {
  p->arr = a;
  p->size = size;
  p->capacity = SIZE;
  
  int i;
  for(i = p->size/2-1; i>=0; i--) {
    //비교, 부모입장에서 자식과 비교 = shift down
    shiftdown(p->arr, i, p->size)
  
  }    
}

void shiftdown(int* arr, int index, int size) {
  int temp;
  int left = (2*index)+1;
  int right = left+1;
  int large = -1;
  if(left < size)
    large = left;
  if(right < size && arr[left] < arr[right])
    large = right;
  if(large != -1 && arr[index] < arr[large]) {
    temp = arr[large];
    arr[large] = arr[index];
    arr[index] = temp;
    shiftdown(arr, large, size); //바꿨는데 그게 또 자식보다 작을 때 재귀호출
  }
}