짱수의 스토리 창고

우선순위 큐와 힙을 비교해 봄으로써 추상적 데이타 타입과 자료구조의 차이를 명확하게 이해할 수 있다.

우선순위 큐는 추상적 데이타 타입(ADT)의 하나로서, ADT가 정의하는 것은 어떤 블랙 박스 같은 것으로,
그 안에 무엇이 어떻게 들어 있는지에는 관심이 없고, '어떤 일을 할 수 있다'에 초점을 맞춘다.
심지어 그 어떤 일을 할 때 얼마의 시간이 걸리는지에 대해서도 별로 관심이 없다.

우선순위 큐는 다음과 같은 일을 할 수 있다.

1. 큐에 '무엇인가'를 넣을 수 있다. 여기에 숫자로 된 우선순위를 꼬리표로 해서 함께 넣는다.
2. 큐에서 가장 높은 우선순위의 꼬리표가 붙은 '무엇인가'를 꺼낼 수 있다.
3. 2번의 변형으로, 가장 높은 우선순위에 무엇이 있는지 볼 수 있다. (꺼내지 않는다)

왜 가장 높은 우선순위의 것만 꺼낼 수 있고, 다른 것을 임의로 꺼낼 수도 없는,
그렇게 제약이 많은 것을 생각하느냐고 할 수도 있겠지만,
ADT에서 중요한 개념은 이것이다. 
시간이나 공간 같은 제약을 고려하지 않고, 한정된 수의 요구사항을 명확히 하는 것.
요구사항이 한정되어야 그 다음에, 어떤 방법으로 구현하는 것이 효율적인지 생각할 수 있기 때문이다.

'배열로 구현하지'라고 먼저 생각해 버리면, 배열에서 효율적으로 동작하는 새로운 기능을 추가할 수도 있겠지만,
일의 순서가 그런 것이 아니기 때문이다.

이렇게 우선순위 큐의 기능을 정의하고 나서, 우선순위 큐를 효율적으로 구현하기 위한 자료구조를 생각해 보자.
메모리에 저장된 형태에 대해서 다음과 같은 것을 생각해 볼 수 있다.

1. 배열 - 여기에는 다시 임의 배열과, 정렬된 배열
2. 리스트 - 역시 임의 리스트와, 정렬된 리스트
3. 그리고 다음에 설명할 힙(Heap)

배열과 리스트가 별도의 자료구조인 것은 명확하지만, 임의로 넣은 것과, 정렬된 상태인 것이 다른 것인 이유는,
배열과 리스트에 대한 연산이 다르듯이, 정렬되었는지 여부에 따라 연산의 구현이 확연하게 달라지기 때문이다.

임의 배열을 사용할 경우 우선순위 큐의 구현은 다음과 같이 이루어진다.
1. 넣을 때 - 현재 들어 있는 것들 뒤에 넣는다. O(1)
2. 꺼낼 때 - 우선순위 값을 비교하여 가장 큰 것을 꺼낸다. O(n)

정렬되어 있는 배열을 사용할 경우 우선순위 큐의 구현은 다음과 같이 이루어진다.
1. 넣을 때 - 정렬된 순서에서의 위치를 찾아서 넣는다. O(n)
2. 꺼낼 때 - 맨 앞의 것을 꺼내면 된다. O(1)

n개를 넣고 꺼낼 때 걸리는 시간은, 둘 다 O(n * n)이 된다.

n개를 다 넣고 나서 - 정렬하고 - n개를 순서대로 꺼내는 것은, 우선순위 큐를 쓰고자 하는 목적에도 맞지 않으며,
우선순위 큐의 정의에 정렬 같은 것은 없다. 
다만 이렇게 했을 때 걸리는 시간은 정렬에 걸리는 시간인 O (n log n)으로 낮출 수 있다.

이제 힙에 대해 얘기해 보자.
힙이라는 자료구조를 가지고 얻고자 하는 것은 임의로 넣고 꺼내는 것을 지원하면서, O(n * n)보다 빠른 방법이다.

이를 위해서 힙이라는 자료구조는 개념상으로 바이너리 트리에서, '부모 노드는 자식 노드보다 크다'라는 가정만
유지한다. 당연히 최상위 루트 노드의 값이 가장 크다. 
이를 배열에 저장했을 때 유지되는 내부 형태는, n번째 항목의 자식 노드는 n * 2와, n * 2 + 1 번째에 위치한다. 
그리고 배열에 들어있는 값들은 정렬된 형태도 아니고, 임의 형태도 아니지만, 
맨 앞에는 가장 우선순위가 큰 값을 갖고 있게 된다.

1. 넣을 때 - 맨 뒤에 넣는다. 그리고 형제 노드, 부모 노드와 비교해서 셋 중에 큰 값을 부모 노드로 만든다.
그리고 위로 전파한다. O(log n)에 수행 가능하다.

2. 꺼낼 때 - 맨 앞의 것을 꺼낸다. 그리고 이 자리에는 자식 노드 둘 중에 큰 값을 갖고 올라온다.
그리고 아래로 전파한다. 역시 O(log n)에 수행 가능하다.

따라서 n개를 넣고 꺼낼 때 걸리는 시간은, O(n log n)이 된다.
전체적으로, 정렬에 걸리는 시간과 같은 복잡도를 갖게 되었다. 

여기서 얘기하는 힙은 정확하게는 Binary Heap의 array implementation 이다.

이와 같이 추상적 데이타 타입이 문제에 초점을 둔다면, 자료구조는 해결에 초점을 두고  있다.
인터페이스와 임플리멘테이션도 이와 비슷하게 생각할 수 있을 것이다.

좀 더 자세한 것은 위키피디아에서 Priority Queue와 Heap을 검색해 보기 바란다.

출처 : http://core.egloos.com/

■ Collection : 오브젝트 집합을 나타내는 가장 기본적인 인터페이스
   □ Set : 중복 요소 없는 오브젝트 집합
      ○ SortedSet : 요소가 자동 올림순으로 정렬된다.
                            삽입되는 요소는 Comparable 인터페이스 속성을 갖고 있지만
                            지정된 Comparator에 의해 받아들여진다.
   □ List : 순서있는 오브젝트 집합, 중복허가, 리스트내의 특정위치에 요소를 넣을 수 있다.
               유저는 위치(인덱스)를 지정하여 각요소에 접근할 수 있다.

■ Map : 키-값으로 나타내는 오브젝트 집합. 키는 중복될 수 없다.
   □ SortedMap : 요소가 키로서 자동 올림순 정렬되는 Map.
                          삽입된 키는 Comparable 인터페이스 속성을 갖고 있지만
                          지정된 Comparator에 의해 받아들여진다.

HashSet   : HashMap 인터페이스를 기본으로 Set인터페이스를 구현한 것. 순서를 보장할 수 없다.

TreeSet    : TreeMap 인터페이스를 기본으로 Set인터페이스를 구현한 것. 올림순으로 소트된다.

LinkedHashSet : 삽입된 순서를 기억한다.
                          같은 요소를 다시 삽입하면 이전 순서를 그대로 기억한다.

ArrayList   : List 인터페이스 속성을 갖고 배열크기를 변경할 수 있다.
                  배열크기를 조작하는 메소드를 제공한다.

LinkedList : 리스트의 처음과 마지막 요소를 삽입,삭제할 수 있다. 
                  그 관련 메소드 제공.
                  동기화되어 있지 않다는 것을 제외하면 Vector와 같다.

HashMap : 동기화되어 있지않다는 것과 Null을 허용한다는 것 이외에는 HashTable과 같다.

TreeMap  : Red-Black Tree. 키의 올림순으로 소트된다.
                  LinkedHashMap : 키가 맵에 삽입된 순서를 기억한다. 
                  같은 키로 삽입해도 이전의 순서를 기억한다.

■HashSet,TreeSet,LinkedHashSet 비교
중복요소없는 오브젝트 집합을 관리하는 클래스에는 HashSet,TreeSet,LinkedHashSet가 있다.
Set기능만 필요한 경우에는 HashSet.
요소를 올림차순으로 정렬하는 경우에는 TreeSet.
요소의 삽입순서를 기억할 필요가 있을 때에는 LinkedHashSet.

■ArrayList와 LinkedList
순서있는 오브젝트 집합을 관리하는 클래스로는 ArrayList와 LinkedList가 있다.

ArrayList는 인덱스에 의한 랜덤엑세스 성능이 좋지만
요소의 삽입, 삭제에는 좋지않다.
LinkedList는 거꾸로 요소의 삽입, 삭제에는 성능이 좋지만
인덱스에 의한 랜덤엑세스는 좋지 않다.

■HashMap, TreeMap, LinkedHashMap 
키-값 관계로 맵핑하는 경우에 사용하는 클래스에는 HashMap, TreeMap, LinkedHashMap이 있다.
Map 기능만 필요한 경우는 HashMap
키를 올림차순으로 소트할 필요가 있을 때는 TreeMap
키의 삽입순서를 기억할 필요가 있을 때에는 LinkedHashMap

■Set Class Test

import java.util.*;

public class SetClassTest {
  public static void main(String[] args) {
    try {
      // HashSet
      Set hashSet = new HashSet();
      addData(hashSet);
      System.out.println("HashSet : " + hashSet);

      // TreeSet
      Set treeSet = new TreeSet();
      addData(treeSet);
      System.out.println("TreeSet : " + treeSet);

      // LinkedHashSet
      Set linkedHashSet = new LinkedHashSet();
      addData(linkedHashSet);
      System.out.println("LinkedHashSet : " + linkedHashSet);

    } catch (Exception e) {
      e.printStackTrace();
    }
  }

  static void addData(Set set) {
    for (int i = 10;i >= 1;i--) {
      set.add(new Integer(i));
    }
  }
}

결과 :

   HashSet : [2,4,8,9,6,1,3,7,10,5]

   TreeSet : [1,2,3,4,5,6,7,8,9,10]

   LinkedHashSet : [10,9,8,7,6,5,4,3,2,1]

■List Class Test

import java.util.*;

public class ListClassTest {
  public static void main(String[] args) {
    try {
      long start, end;
      /** 추가 **/
      // ArrayList
      List arrayList = new ArrayList();
      start = System.currentTimeMillis();
      addData(arrayList);
      end = System.currentTimeMillis();
      System.out.println("ArrayList 추가 : " + (end - start));

      // LinkedList
      List linkedList = new LinkedList();
      start = System.currentTimeMillis();
      addData(linkedList);
      end = System.currentTimeMillis();
      System.out.println("LinkedList 추가 : " + (end - start));

      /** 삭제 **/
      // ArrayList
      start = System.currentTimeMillis();
      removeData(arrayList);
      end = System.currentTimeMillis();
      System.out.println("ArrayList 삭제 : " + (end - start));

      // LinkedList
      start = System.currentTimeMillis();
      removeData(linkedList);
      end = System.currentTimeMillis();
      System.out.println("LinkedList 삭제 : " + (end - start));

      /** 삽입 **/
      // ArrayList
      start = System.currentTimeMillis();
      insertData(arrayList);
      end = System.currentTimeMillis();
      System.out.println("ArrayList 삽입 : " + (end - start));

      // LinkedList
      start = System.currentTimeMillis();
      insertData(linkedList);
      end = System.currentTimeMillis();
      System.out.println("LinkedList 삽입 : " + (end - start));

      /**  인덱스 접근 **/
      // ArrayList
      start = System.currentTimeMillis();
      indexAccess(arrayList);
      end = System.currentTimeMillis();
      System.out.println("ArrayList 인덱스 접근 : " + (end - start));

      // LinkedList
      start = System.currentTimeMillis();
      indexAccess(linkedList);
      end = System.currentTimeMillis();
      System.out.println("LinkedList 인덱스 접근 : " + (end - start));

      /** Iterator 로 접근 **/
      // ArrayList
      start = System.currentTimeMillis();
      iteratorAccess(arrayList);
      end = System.currentTimeMillis();
      System.out.println("ArrayList Iterator로 접근 : " + (end - start));

      // LinkedList
      start = System.currentTimeMillis();
      iteratorAccess(linkedList);
      end = System.currentTimeMillis();
      System.out.println("LinkedList Iterator로 접근 : " + (end - start));

    } catch (Exception e) {
      e.printStackTrace();
    }
  }
  static void addData(List list) {
    for (int i=1;i<100000;i++) {
      list.add(new Integer(i));
    }
  }
  static void removeData(List list) {
    while(!list.isEmpty()) {
      list.remove(0);
    }
  }
  static void insertData(List list) {
    for (int i=1;i<100000;i++) {
      list.add(0 , new Integer(i));
    }
  }

  static void indexAccess(List list) {
    int size = list.size();
    for (int i=0;i<size;i++) {
      Integer integer = (Integer)list.get(i);
    }
  }
  static void iteratorAccess(List list) {
    Iterator iterator = list.iterator();
    while (iterator.hasNext()) {
      Integer integer = (Integer)iterator.next();
    }
  }
}

결과 :

  ArrayList 추가 : 451

  LinkedList 추가 : 230

  ArrayList 삭제 : 45315

  LinkedList 삭제 : 20

  ArrayList 삽입 : 45416

  LinkedList 삽입 : 170

  ArrayList 인덱스로 접근 : 0

  LinkedList 인덱스로 접근 : 231473

  ArrayList Iterator로 접근 : 60

  LinkedList Iterator로 접근 : 50

■Map Class Test

import java.util.*;

public class MapClassTest {
  public static void main(String[] args) {
    try {
      // HashMap
      Map hashMap = new HashMap();
      putData(hashMap);
      System.out.println("HashMap : " + hashMap);

      // TreeMap
      Map treeMap = new TreeMap();
      putData(treeMap);
      System.out.println("TreeMap : " + treeMap);

      // LinkedHashMap
      Map linkedHashMap = new LinkedHashMap();
      putData(linkedHashMap);
      System.out.println("LinkedHashMap : " + linkedHashMap);

    } catch (Exception e) {
      e.printStackTrace();
    }
  }
  static void putData(Map map) {
    map.put("5" , "Five");
    map.put("4" , "Four");
    map.put("3" , "Three");
    map.put("2" , "Two");
    map.put("1" , "One");
  }
}

결과 :

HashMap : {3=Three, 5=Five, 2=Two, 4=Four, 1=One}

TreeMap : {1=One, 2=Two, 3=Three, 4=Four, 5=Five}

LinkedHashMap : {5=Five, 4=Four, 3=Three, 2=Two, 1=One}

출처 : http://dojeun.egloos.com