Heap 구현(C)

heap

힙은 주어진 데이터들 중에서 특정 기준에 부합하는 '최대' 혹은 '최소'를 빠르게 찾아낼 수 있는 자료구조이다.

힙은 완전이진트리 를 기반으로 한다. 완전이진트리란 하나의 부모당 자식이 최대 2개까지만 존재하는 트리중에서 왼쪽부터 차례대로 삽입된 형태를 가진 트리를 말한다.

부모노드의 값이 자식노드 보다 클때는 "최대힙" 작은 때에는 "최소힙"이라고 부른다.

힙에서는 "형제노드" 간의 관계는 존재하지 않는다. 오로지 자식노드만을 비교한다.
즉, 최대힙을 가정했을 때, 트리의 가장 꼭대기 층에 있는 추트노의 값이 트리에 존재하는 값들 중 가장 큰 값이다.

힙의 장점

기본적인 정렬은 nlogn이다. 따라서 전체 어레이값들에 대해서 작은 값부터 하나씩 가져온다면, nlogn이 필요하다. 힙을 사용하다해도 삽입에 logn이 들고 삭제때에도 logn이 들기에 nlogn이 든다. 하지만, 값을 하나씩 넣으면서 그때마다 최솟값을 찾는다면? 단순 정렬이라면 새로운 값을 넣을 때마다 정렬을 해야할 것이고 이는 n * nlogn이 들어간다. 하지만 heap의 경우는 root값만 읽어오면 되기에 단순히 nlogn이 들어간다.

작동원리

삽입

1. 트리의 가장 마지막 노드 다음에 현재 삽입하고자 하는 데이터를 넣어준다.
2. 부모노드와 비교하면서 부모노드보다 더 큰 값이라면 부모노드와 swap해준다.
3. 2번 조건을 만족하지 않을 때까지 혹은 루트노드가 아닐 때까지 반복한다.

삭제

1. 가져올 최대값을 미리 저장해둔다.
2. 가장 마지막 노드의 값과 루트노드의 값을 swap해준다.
3. 현재 노드에서 자식노드와 비교하면서 더 작은 값이라면 swap해준다. (swap할 때 형제중에 더 큰값이랑 swap한다)
4. 위치를 찾을 때까지 3번 과정을 반복한다.
5. 미리 저장해둔 최댓값을 return 시켜주고, 힙의 크기를 1 감소시킨다.

구현

물론 트리구조도 가능하지만, Array에서 heap 구조를 만들 수 있다.

* 루트의 인덱스를 1로 설정한다면,부모노드의 번호는 자식노드의 번호 / 2 이고, 자식노드의 번호는 부모노드의 번호 2 or 부모번호 *2 + 1 이다.

 void push(int data) {
     int idx = ++heap_idx; // 추가된 data의 idx
    heap[idx] = data;
    while((idx != 1) && (data > heap[idx / 2])) { // 부모노드가 더 크다면 스위치
        swap(heap[idx], heap[idx/2]);
        idx = idx / 2;
    }
 }

 int pop(int data) {
     int result = heap[1];
     swap(heap[1], heap[heap_idx--]);
    int parent = 1;
    while(true) {
        int child = parent * 2;
        if(child +1 <= heap_idx && heap[child] < heap[child+1]) child++; // 자식 두개가 존재한다면, 둘중에 큰걸 child에
        if(child > heap_idx || heap[child] < heap[parent]) break; // child가 heap범위를 넘거나, 부모가 더 크다면 break
        swap(heap[child], heap[parernt]);
        parent = child;
    }

    return result;
 }