[알고리즘/C, C++] 최대 힙 구현하기

Goal

최대 힙(maxHeap) 구조
시간복잡도
힙(heap)의 삽입
힙(heap)의 삭제

최대 힙(maxHeap) 구조

배열로 구현한다.
부모노드가 자식노드보다 항상 큰 값을 갖는다.
*index가 1부터 시작하도록 해서 자식노드와 부모노드의 index를 계산하기 쉽게 한다.

시간복잡도

Worst : O(nlogn)
Average : O(nlogn)
*Best : O(nlogn)

힙(heap)의 삽입

1. 트리의 가장 끝에 삽입하는 원소를 추가한다.
2. 삽입한 원소와 해당 원소의 부모노드의 크기를 바꿔가며 위치를 찾는다.(Heapify)

void push(int x){
    heap[++heapCount] = x;
    
    int child = heapCount;
    int parent = child/2;
    
    while(child>1 && heap[child]>heap[parent]){
        swap(&heap[child], &heap[parent]);
        child = parent;
        parent = child/2;
    }
    
}

힙(heap)의 삭제

1. 트리의 가장 첫번째 원소를 반환한다.
2. 가장 첫번째 원소와 가장 마지막 원소를 swap한다.
3. 트리의 크기를 1감소시킨다.
4. 마지막 원소와 해당 원소의 부모노드의 크기를 바꿔가며 위치를 찾는다.(Heapify)

int pop(){
    int ret = heap[1];
    
    swap(&heap[1], &heap[heapCount]);
    heapCount = heapCount-1;
    
    int parent = 1;
    int child = parent*2;
    
    if(child+1 <= heapCount){
        child = (heap[child]>heap[child+1]) ? child : child+1;
    }
    
    while(child<=heapCount && heap[child]>heap[parent]){
        swap(&heap[child], &heap[parent]);
        parent = child;
        child = parent*2;
        
        if(child+1 <= heapCount){
            child = (heap[child]>heap[child+1])? child : child+1;
        }
    }
    
    return ret;
}

전체 소스코드

#include <stdio.h>
#define HEAP_SIZE 256
#define ARRAY_SIZE 10

using namespace std;
int heap[HEAP_SIZE];
int heapCount = 0;

void swap(int *a, int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void push(int x){
    heap[++heapCount] = x;
    
    int child = heapCount;
    int parent = child/2;
    
    while(child>1 && heap[child]>heap[parent]){
        swap(&heap[child], &heap[parent]);
        child = parent;
        parent = child/2;
    }
    
}

int pop(){
    int ret = heap[1];
    
    swap(&heap[1], &heap[heapCount]);
    heapCount = heapCount-1;
    
    int parent = 1;
    int child = parent*2;
    
    if(child+1 <= heapCount){
        child = (heap[child]>heap[child+1]) ? child : child+1;
    }
    
    while(child<=heapCount && heap[child]>heap[parent]){
        swap(&heap[child], &heap[parent]);
        parent = child;
        child = parent*2;
        
        if(child+1 <= heapCount){
            child = (heap[child]>heap[child+1])? child : child+1;
        }
    }
    
    return ret;
}


int main(){
    
    int a[ARRAY_SIZE] = {5,6,3,7,9,8,1,2,4,10};
    //최대 힙에 a[0]~a[9]까지 삽입.
    printf("Push : ");
    for(int i = 0 ; i<ARRAY_SIZE ; i++){
        printf("%d ", a[i]);
        push(a[i]);
    }
    printf("\n");
    
    
    printf("Pop : ");
    //최대 힙에서 차례대로 pop()한 결과.
    for(int i = 0 ; i<ARRAY_SIZE ; i++){
        printf("%d ", pop());
    }
    printf("\n");
    return 0;
}

---

실행 결과

Push : 5 6 3 7 9 8 1 2 4 10
Pop : 10 9 8 7 6 5 4 3 2 1
Program ended with exit code: 0