오늘은 자료구조중에 이진트리에서의 힙의 삽입에 대한 내용을 작성해보려 합니다.

힙이란 완전 이진 트리에 있는 노드중에 키값이 큰지 직은지 찾기 위한 자료구조입니다.

키 값이 가장 큰 노드를 우선 배치하면 maxheap이라고 하고, 가장 작은 노드부터 배치하면 minheap입니다.

최대힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 크거나 같은 노드 관계이며, 최소힙에서는 부모 노트의 키값이 자식 노드의 키값보가 항상 작거나 같습니다.

그래서 최대 힙의 루트는 가장 큰 값이고, 최소 힙의 루트는 가장 작은 값이 됩니다.

일반적으로 힙은 maxheap, 최대 힙을 의미한다고 합니다.

힙 삽입

힙에서의 삽입은 완전 이진트리를 유지하기 위해 현재의 마지막 노드의 다음 자리를 확장하여 만든 자리에 삽입할 노드를 임시로 저장하고 키값의 관계가 최대 힙이 되도록 다시 만들기 위해 삽입한 노드의 값을 부모노드의 값과 비교합니다.

힙에서의 삽입은 어느 위치에서든지 상위 노드를 찾아야 되기 때문에 순차 자료구조 방식을 이용하여 힙을 표현합니다.

배열의 인덱스 관계를 이용하여 상위 노드를 찾을 수 있습니다.

알고리즘

func()
    if(n = heapsize) then heapfull();
    n <- n+1;
    for(i < n;;) do {
        if(i =1) then exit;
        if(item <= heap[i/2]) then exit;
        heap[i] <- heap[i/2];
        i <- i/2;
    }
    heap[i] <- item;
end()

코드

public void insert(int item){
    int i = ++size;
    while(i != 1&&item > itemheap[i/2]){
        itemheap[i] = itemheap[i/2];
        i /=2;
    }
    itemheap[i] = item;
}