(basic) 힙구현, 우선순위큐, Comparable/tor

 본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다.

목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. 

 

- 힙

- 우선순위큐

- Comparable

 

 

- 힙

 

heap은 트리이다.

가장 큰 원소를 찾는데 최적화된 형태의 이진트리이다.(minheap,maxheap은 연산자 차이밖에없음)

추가와 꺼내는 연산 모두 O(logN) 에 수행한다.

힙은 대부분의 프로그래밍 언어의 표준 라이브러이에 포함되어 있기 떄문에, 직접 구현할 일은 거의 없다.

 

힙은 다음과 같은 특징은 지녔다.

- 부모노드와 자식관계만 적용되며 부모노드는 자식보다 커야하며 자식간의 관계는 생각하지 않는다.

- 마지막 레벨을 제외한 모든 레벨이 노드가 꽉 차 있어야 한다.

- 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.

 

힙은 대소 관계 조건이 이진 검색 트리가 요구하는 조건보다 느슨해서 구현이 그렇게 복잡하지는 않다.

 

 

 

 

- 우선순위큐

 

Queue란 FIFO(First In First Out)이며

PriorityQueue는 우선순위에 따라서 나오는것이다.

가장 먼저 입력된 자료가 가장 먼저 꺼내지는 것이 아니라, 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다.

 

배열, 연결리스트로 구현하는방법이 있으나 이는 추가적인 연산으로 비효율적이다.

그러므로 Heap을 사용하여서 구현하는것이다.

 

우선순위큐는 현재 넣은 수들의 최대 혹은 최소밖에 모른다.

 

자세한 설명은 아래와 블로그에서 확인가능하다.

http://asuraiv.blogspot.com/2015/11/java-priorityqueue.html

[JAVA] 우선순위(PriorityQueue) 큐

아래와 같이 사용가능하다.

 public Jewel_Info implements Comparable<Jewel_Info>{
 	//bulabula...
    public int compareTo(Jewel_Info ObjforCompare) {
        if(this.Jewel_Info_Weight == ObjforCompare.Jewel_Info_Weight){
            if(this.Jewel_Info_Price >= ObjforCompare.Jewel_Info_Price)
                return 1;
            else    
                return -1;
        }
        else{
            if(this.Jewel_Info_Weight > ObjforCompare.Jewel_Info_Weight)
                return 1;
            else
                return -1;
        }
    }
}
main class{
 PriorityQueue<Jewel_Info> priorityQueue = new PriorityQueue<Jewel_Info>();
}

comapreTo나 compare를 생성하지 않으면 에러가 발생한다.

 

 

 

- Comparable<T>, Comparator<T>

 

1. Comparable : 기본적으로 오름차순으로정렬

int compareTo(T o) : 해당 객체와 전달된 객체의 순서를 비교해서

양수면 자리를 바꾸고, 0이나 음수면 자리를 유지한다.

 

2. Comparator : 오름차순 이외의 기준으로도 정렬할수 있게 됨

int compare(T o1, T o2) : 전달된 두 객체의 순서를 비교함