Heap

Heap?

트리 안에 있는 원소들이 서로 비교될 수 있는 이진트리이다.
힙은 다음과 같은 두 가지 규칙이 있는 이진트리이다.

1. 각 노드의 값은 그 노드의 자식들의 값보다 같거나 크다. (max heap의 경우)
2. 이 트리는 complete binary tree (완전 이진 트리) 이므로 가장 깊은 노드들을 제외한 나머지 노드들은 가능한 한 많은 자식들을 가져야 한다.

heap의 각 노드는 우선순위를 가진 원소를 하나 포함한다.
heap의 규칙은 다음과 같다.

1. 각 노드의 원소는 자식 노드의 원소에 대해 같거나 더 높은 우선순위를 가진다.
2. 이 트리는 완전이진트리이다.

Operations

adding

Reheapification upward의 성격을 가진다.
절차는 아래와 같다.

1. 새로운 원소를 heap의 가능한 자리에 넣는다. 이것은 완전이진트리가 되어야 하지만 heap은 아니다.
2. 새로운 노드가 부모노드보다 높은 우선순위를 가지는 동안 부모와 노드의 위치를 swap한다.

구현된 코드는 아래와 같다.

    public void heapUp(int element){
        int pos = size;
        Heap[size++] = element;
        while(Heap[parent(pos)] < Heap[pos]){
            swap(parent(pos), pos);
            pos = parent(pos);
        }
    }

removing

우선순위 큐에서 원소를 제거하는 것은 heap의 root 노드를 제거하는 것과 같다.
reheapification downward의 성격을 가진다.
절차는 아래와 같다.

1. root 노드의 값을 return 한다.
2. 가장 깊은 레벨의 마지막 원소를 root에 올리고 기존의 노드를 트리에서 제거한다.
3. 이 노드가 자식의 우선순위보다 낮은 우선순위를 가지는 동안 자식노드와 이 노드의 위치를 swap한다. 단 가장 높은 우선순위를 가지는 자식과 swap해야한다.

구현된 코드는 아래와 같다.

    public void heapDown(int pos){
        if(isLeaf(pos))
            return;
        if(Heap[pos] < Heap[leftChild(pos)] || Heap[pos] < Heap[rightChild(pos)]){

            if(Heap[leftChild(pos)] > Heap[rightChild(pos)]){
                swap(pos, leftChild(pos));
                heapDown(leftChild(pos));
            }else{
                swap(pos, rightChild(pos));
                heapDown(rightChild(pos));
            }
        }
    }

구현

구현된 코드는 아래와 같다.

public class MaxHeap{
    private int[] Heap;
    private int size;
    private int maxsize;

    public MaxHeap(int maxsize){
        this.maxsize = maxsize;
        this.size = 0;
        Heap = new int[this.maxsize];
    }


    private int parent(int pos){
        return (pos-1)/2;
    }

    private int leftChild(int pos){
        return (2*pos+1);
    }

    private int rightChild(int pos){
        return (2*pos+2);
    }

    private boolean isLeaf(int pos){
        if((size/2) < pos && pos <= size){
            return true;
        }
        return false;
    }

    private void swap(int fpos, int spos){
        int tmp;
        tmp = Heap[fpos];
        Heap[fpos] = Heap[spos];
        Heap[spos] = tmp;
    }

    public void heapUp(int element){
        int pos = size;
        Heap[size++] = element;
        while(Heap[parent(pos)] < Heap[pos]){
            swap(parent(pos), pos);
            pos = parent(pos);
        }
    }

    public void heapDown(int pos){
        if(isLeaf(pos))
            return;
        if(Heap[pos] < Heap[leftChild(pos)] || Heap[pos] < Heap[rightChild(pos)]){

            if(Heap[leftChild(pos)] > Heap[rightChild(pos)]){
                swap(pos, leftChild(pos));
                heapDown(leftChild(pos));
            }else{
                swap(pos, rightChild(pos));
                heapDown(rightChild(pos));
            }
        }
    }

}