[자료구조] HEAP(힙)

Contents

1. Heap과 이진트리/완전이진트리/이진탐색트리란?

2 배열/연결리스트로 우선순위 큐 구현한다면?

3. HEAP 이용해 우선순위 큐 구현하기

 

1. 힙(Heap)

---

- 최대값과 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 *완전이진트리를 기본으로 한 자료구조이다.
하지만 *이진탐색트리와 달리 중복값이 허용된다.

- 우선순위 큐를 위해 만들어진 자료구조로, 이미 많은 언어에서 이미 구현된 우선순위 큐 라이브러리를 제공한다.

 

*우선순위 큐란? 일반적인 큐는 FIFO구조이지만, 우선순위 큐는 각 원소들이 우선순위를 가지고 있으며 우선순위 큐에서 높은 우선순위를 가진 것부터 먼저 처리되는 구조이다. 

* 여기서 잠깐! 완전이진트리, 이진트리, 이진탐색트리 용어에 대해서도 알고가자.

1. 이진트리란?  각각의 노드가 최대 2개의 자식 노드를 가지는 트리 자료구조이다.

 

2, 완전이진트리란? 이진트리중 왼쪽부터 차례대로 채워져 있는 트리를 말한다.

(왼) 완전이진트리 (오) 이진트리

왼쪽 그림은 마지막 레벨을 제외한 모든 레벨이 모두 채워져 있으며, 왼쪽부터 차례대로 채워져 있어 완전이진트리라 부른다.

오른쪽 그림은 왼쪽부터 차례대로 채워져 있이 않아 완전이진트리가 아닌 이진트리라고만 할 수 있다.

 

3.  이진탐색트리란?

- 각 노드의 왼쪽 서브트리는 해당 노드보다 작은 값, 오른쪽 서브트리는 해당 노드보다 큰 값을 지닌 노드들로 이루어져 있다. 즉, 정렬된 상태라는 것이다.
- 중복된 노드가 없어야 한다.

 

힙 종류는 최대힙과 최소힙이 있다.

최대힙은 부모노드가 가장 크고 최소힙은 부모노드가 가장 작은 속성을 가지고 있다. 이를 통해 최대값과 최소값 연산을 빠르게 찾아낼 수 있다.

 

2. 배열과 연결리스트 이용해 우선순위 큐 구현한다면?

---

1. 배열 이용하기

0번째 인덱스는 편하게 구현하기 위해서 사용하지 않는다.

i번째 인덱스에 대해서 각각의 자식노드는 i*2, i*2+1로 나타낼 수 있으며 부모의 인덱스는 자식의 인덱스/2이다.

HEAP 배열 이용해 구현하기

노드 수가 많이 질수록 메모리 낭비가 심하고 삽입/삭제시 레벨 변경으로 인한 데이터 이동이 발생한다.

 

2. 연결리스트 이용하기

각 노드는 data필드, 왼쪽 서브트리 가르키는 필드, 오른쪽 서브트리 가르키는 필드로 구성된다.

삽입의 위치를 찾기 위해 모든 노드를 비교해야 할지도 모르며 이 또한 배열과 같이 성능 저하가 발생한다.

 

그러므로 우선순위 큐를 구할 땐 HEAP이란 자료구조를 이용해서 구현하는 것이 일반적이다.

 

3. HEAP 이용해 우선순위 큐 구현하기

---

최대 힙으로 최대 우선순위 큐를 구현하게 되고 최소 힙으로 최소 우선순위 큐를 구현하게 된다.

그렇다면 이 최대힙과 최소힙 즉, 완전이진트리는 어떻게 구현할 것인가? 특정 인덱스에 바로 접근하기 좋은 배열이 연결리스트보다 좀 더 효율적이다. 배열 기반으로 구현한 HEAP을 이용해 우선순위 큐를 구현하는 것이다.

 

PriortiyQueue 내부 동작이 heap에 의해 이루어진다는 것을 알았으니 자바 라이브러리에서 제공하는 PriorityQueue를 이용해보자.

public class PriorityQueueImpl {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.add(1); //큐가 꽉 차 있어, 추가 실패시 예외를 발생시킨다
        priorityQueue.offer(3); //큐가 꽉 차 있어, 추가 실패시 false를 리턴한다.
        priorityQueue.offer(10);
        priorityQueue.offer(5);
        priorityQueue.offer(8);

        while(!priorityQueue.isEmpty()){
            System.out.println(priorityQueue.poll());
        }
    }
}

/*출력*/
1
3
5
8
10

기본적으로 정수형에 대해서는 오름차순 정렬(최소힙)을 한다.

내림차순 정렬(최대힙)을 우선순위 기준으로 두고 싶다면 Collections.reverseOrder()를 PriorityQueue의 생성자 매개변수로 넘겨준다.

public class PriorityQueueImpl {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
        priorityQueue.add(1); 
        priorityQueue.offer(3); 
        priorityQueue.offer(10);
        priorityQueue.offer(5);
        priorityQueue.offer(8);

        while(!priorityQueue.isEmpty()){
            System.out.println(priorityQueue.poll());
        }
    }
}

/*출력*/
10
8
5
3
1

 

특정한 정렬 기준을 만들고 싶다면? Comparator을 사용한다.

public class PriorityQueueImpl {
    public static void main(String[] args) {
        PriorityQueue<Person> priorityQueue = new PriorityQueue<>(new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                return o1.age-o2.age;//오름차순
            }
        });
        priorityQueue.offer(new Person("John", 18));
        priorityQueue.offer(new Person("Amy", 25));
        priorityQueue.offer(new Person("kris", 30));
        priorityQueue.offer(new Person("kathy", 20));
        priorityQueue.offer(new Person("jun", 23));


        while(!priorityQueue.isEmpty()){
            System.out.println(priorityQueue.poll().age);
        }
    }

    public static class Person{
        private String name;
        private int age;

        public Person(String name, int age){
            this.name = name;
            this.age = age;
        }
    }
}

/*출력*/
18
20
23
25
30

역순으로 뽑아내고 싶다면 정렬기준을 역순으로 재정의해주면 된다.

PriorityQueue<Person> priorityQueue = new PriorityQueue<>(new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                return o2.age-o1.age;//내림차순
            }
        });

/*출력*/
30
25
23
20
18