Heap

[자료구조 복습]
Heap이란 다음의 성질을 만족하는 이진트리다.

Heap : Heap is a complete binary tree in which the key value in each node is no smaller(larger) than the key values in its children.
즉 모든 노드에 대해 부모는 자식보다 항상 크거나, 항상 작다면 max heap 또는 min heap인 것이다.
Heap은 priority queue 구현에 자주 이용된다고 한다(난 잘 모름).
일단 Heap은 complete binary tree이기 때문에 배열로 구현해도 memory 낭비가 크지 않다. 이 경우에 search는 O(n)에 가능하다.
Heap operations

• push
• pop

Heap 연산은 기본적으로 두 가지 있는데 push와 pop이다. 코드가 어렵지 않으니 코드부터 보자.

#define HEAP_MAX_SIZE 100
int heap[HEAP_MAX_SIZE];
int heap_size = 0;

전역변수 선언

void heap_insert(int value) {
    int i;
    if (heap_size== HEAP_MAX_SIZE - 1) {
        fprintf(stdout, "Heap is full\n");
        return;
    }
    heap_size++;
    i = heap_size;
    while ((i != 1) && value > heap[i>>1]) {
        heap[i] = heap[i>>1];
        i >>= 1;
    }
    heap[i] = value;
}

insert가 동작하는 것을 보면 다음과 같다.

기존에 n까지 Heap에 저장되어 있다면 n+1 위치에 우선 삽입한다. 그 후 parent 와 비교하며 끌어 내리는 방식인데 이를 bubbling up이라고 한다.

이진트리이기 때문에 시간복잡도는 O(log n).

int heap_delete() {
    int parent=1, child=2;
    int res = heap[1];
    int temp;
    if (!heap_size) {
      fprintf(stdout,"Heap is empty\n");
      exit(EXIT_FAILURE);
    }
    temp = heap[heap_size--];
    while (child <= heap_size) {
      if (heap[child] < heap[child + 1] && child < heap_size)
          child++;
      if (temp >= heap[child]) break;
      heap[parent] = heap[child];
      parent = child;
      child <<= 1;
    }
    heap[parent] = temp;
    return res;
}

delete는 항상 root값을 pop하는 방식이다.

parent가 빌 경우 child 중에 한 노드를 parent로 올리는 것을 반복하며 채운다. 이때 맨 heap의 총 사이즈가 1 줄었기 때문에 마지막 노드가 이동해야 하는데 노드가 올라가면서 생기는 빈자리 중 알맞은 자리에 위치하게 된다.

delete 역시 시간복잡도는 O(log n).

void adjust(int root_idx, int size) {
    int child, root_value;
 
    root_value = heap[root_idx];
    child = root_idx<<1;
    while (child <= size) {
        if (child < size && (heap[child] < heap[child + 1]))
             child++;
        if (root_value > heap[child]) break;
        heap[child>>1] = heap[child];
        child <<= 1;
    }
    heap[child >> 1] = root_value;
}

void heap_sort() {
    for (int i = heap_size >> 1; i > 0; i--) {
        adjust(i, heap_size);
    }
    for (int i = heap_size - 1; i > 0; i--) {
        int temp=heap[1];
        heap[1] = heap[i + 1];
        heap[i + 1] = temp;
        adjust(1, i);
    }
}

만들어진 Heap을 정렬하고 싶을땐 어떻게 할까?

Heap sort의 첫번째 반복문이 하는 일은 난수가 저장된 배열을 heapify 하는 것이다. Subtree들을 아래서부터 위까지 Heap 형태로 가꾸는 방식이다.

이렇게 만들어진 Heap을 정렬하는데 Heap 형태로 저장된 값들을 배열형태로 정렬하는 것이다. 코드를 돌려보면 알겠지만 root값을 맨 뒤로 빼고 나머지 값들을 다시 힙 형태로 만든다. 이를 반복하면 전체 힙이 배열형태로 정렬된다.

Heap 정렬의 시간복잡도는 O(n) + O(nlog n) = O(nlog n).