4. 히프 트리(Heap Tree)

히프 트리

삽입은 일반적인 큐와 같이 맨 마지막에 삽입이 되고 삭제의 경우 우선순위 큐의 형태로 삭제되는 트리이다. 중요한 점은 부모는 항상 자식보다 크면 최대 힙, 자식보다 작으면 최 소힙이다. 히프트리는 완전 이진 트리로 배열로 구현한다.

최대히프의 삽입

먼저 가장 트리의 마지막 위치에 삽입한 뒤, 부모와 비교하며 올라간다.

최대히프의 삭제

우선순위가 가장 높은 루트를 삭제하고 가장 마지막 노드를 임시적으로 루트에 배치하여 좌우 자식과 비교하며 노드를 내린다.

class heap{
private:
    int[] tree;
    int capacity;
    int size;
public:
    heap(){
        capacity=100;
        size=1;
        tree=new int[capacity];
    }

    //최대 히프 트리의 삽입
    void insert(int key){
        if(capacity==size)
            return;
        
		int p = index/2;
        int c = index;
        for(;c!=1;){
            if(key>tree[p]){ //삽입될 값과 부모를 비교
                tree[c]=tree[p]; //부모가 삽입될 값보다 작을 경우 교체
                c=p;
                p=p/2;
            }else
                break;
        }
        tree[c]=key;
        size++;
    }

    int remove(){
        if(index == 1)
            return -1;
        int rootValue = tree[1];
        int value = tree[--index]; //마지막 값
        int parent = 1;
        int child = 2;
        for(;child < index;){ //마지막 값 제외
            if(child<index+1 && tree[child]<tree[child+1])
                child++;
            if(tree[child] < value)
                break;
            tree[parent] = tree[child];
            parent = child;
            child*=2;
        }
        tree[parent] = value;
        return rootValue;
    }

    void print(){
        for(int i=1; i<size; i++){
            System.out.print(tree[i]+' ');
        }
    }
};

 

삽입, 삭제 모두 최악의 경우 트리의 높이 만큼 순회하기 때문에 O(logn)의 시간 복잡도를 갖는다.

요약

힙(Heap)은 완전 이진 트리의 일종으로 삽입은 가장 마지막 노드에, 삭제는 우선순위 순서대로 진행되는 자료구조이다. 이는 우선순위 큐(Priority Queue)를 구현하는데 사용된다.