[Java] Heap

 

1. Heap

 

• 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조.
• 무언가를 차곡차곡 쌓아 올린 더미
• 부모의 값은 항상 자식(들)의 값보다…
  • 크거나 같은 최대 힙(Max heap)
  • 작거나 같은 최소 힙(Min heap)
• 데이터의 삽입과 삭제는 모두 O(log⁡N)이 소요. (완전 이진 트리일 때)

 

---

가. 데이터 삽입

 

 

1. 가장 끝의 자리에 노드를 삽입한다.
2. 그 노드와 부모 노드를 서로 비교한다.
3. 규칙에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다.
4. 규칙에 맞을 때까지 반복한다.

 

---

나. 데이터 삭제

 

 

최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다.

 

1. 루트 노드를 제거한다.
2. 루트 자리에 가장 마지막 노드를 삽입한다.
3. 올라간 노드와 그의 자식 노드(들)와 비교한다.
4. 조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다.

• 최대 힙
  1. 부모보다 더 큰 자식이 없으면 교환하지 않고 끝낸다.
  2. 부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환하면 된다.
  3. 부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환한다.
• 최소 힙
  1. 부모보다 더 작은 자식이 없으면 교환하지 않고 끝낸다.
  2. 부모보다 더 작은 자식이 하나만 있으면 그 자식하고 교환하면 된다.
  3. 부모보다 더 작은 자식이 둘 있으면 자식들 중 작은 값과 교환한다.

5. 조건을 만족할 때까지 4의 과정을 반복한다.

 

우선순위 큐(priority queue)를 구현하거나, 힙 정렬(heap sort)을 만들 때 사용된다.

 

출처 : https://namu.wiki/w/힙 트리

 

---

다. 구현

 

최소힙 예시

public class minHeap{
    private ArrayList<Integer> heap;

    //최소힙 생성자
    public minHeap() {
        heap = new ArrayList<Integer>();
        heap.add(0); // 0번째 인덱스는 사용 안합
    }

    //삽입
    public void insert(int val) {
        heap.add(val);
        int p = heap.size()-1;    //p는 새로 삽입한 노드의 인덱스 정보
        while(p>1 && heap.get(p/2)>heap.get(p)) {
            //새로 삽입한 노드의 위치가 1 초과이고 부모가 자식보다 크면 진행 -> 새로 삽입한 노드의 위치가 루트까지 가거나 새로 삽입한 노드가 부모보다 클때까지 진행
            int tmp = heap.get(p/2);//부모 노드의 값
            heap.set(p/2, val);
            heap.set(p, tmp);

            p /= 2;    //새로 삽입한 노드가 한 레벨 상승했으니 인덱스 부모 노드 인덱스 값으로 변경
        }
    }
    //삭제
    public int delete() {
        //힙이 비어있으면 0 리턴
        if(heap.size()-1 < 1) {
            return 0;
        }

        //삭제할 노드, 루트 노드
        int deleteitem = heap.get(1);

        //마지막 노드를root에 삽입하고 마지막 노드 삭제
        heap.set(1,heap.get(heap.size()-1));
        heap.remove(heap.size()-1);

        int pos = 1; //루트에 새로 삽입한 노드의 인덱스 정보

        //pos*2는 왼쪽자식의 인덱스 값, 자식의 인덱스 값이 힙의 사이즈 값보다 크다는것은 더이상 삽입할 위치를 벗어났다는뜻 
        while((pos*2)<heap.size()) {
            int min = heap.get(pos*2);//왼쪽 자식의 값
            int minPos = pos*2;// 왼쪽 자식의 인덱스 값

            //오른쪽 자식의 인덱스가 사이즈보다 작고 왼쪽 보다 더 작을때 오른쪽 자식을 부모와 바꿔줄 자식으로 지정
            if(((pos*2+1)<heap.size()) && min > heap.get(pos*2+1)) {    
                min = heap.get(pos*2 +1);
                minPos = pos*2 +1;
            }

            //부모가 더 작으면 그만
            if(min > heap.get(pos))
                break;

            //부모 자식 교환
            int tmp = heap.get(pos);
            heap.set(pos,heap.get(minPos));
            heap.set(minPos, tmp);
            pos = minPos;
        }

        return deleteitem;
    }

}

(코드 출처 : https://go-coding.tistory.com/25)

 

---

라. 관련 문제

 

1927번: 최소 힙

 

11279번: 최대 힙

 

11286번: 절댓값 힙

 

---

5. Priority Queue

package lacture;

import java.util.PriorityQueue;

public class PQtest {

    public static void main(String[] args) {
        PriorityQueue<Data> pq = new PriorityQueue<>((d1,d2)-> Integer.compare(d1.x, d2.x));

        pq.offer(new Data(3));    
        Data d = new Data(7);
        pq.offer(d);    
        pq.offer(new Data(5));    
        System.out.println(pq); // [[x=3], [x=7], [x=5]]

        d.x = 2; // 바꿔도 힙은 변화하지 않음.
        System.out.println(pq); // [[x=3], [x=2], [x=5]]

        pq.remove(d);    
        pq.offer(d); // 값을 수정하면 다시 뺏다 넣어야 한다.
        System.out.println(pq); // [[x=2], [x=5], [x=3]]

    }

    static class Data {
        int x;
        Data(int x){
            this.x = x;
        }

        @Override
        public String toString() {
            return "[x=" + x + "]";
        }
    }

}
/*
[[x=3], [x=7], [x=5]]
[[x=3], [x=2], [x=5]]
[[x=2], [x=5], [x=3]]
*/

• System.out.println(pq);
  : PQ 내부적으로 Heap을 사용하고 있는 것을 알 수 있다.
  : 최소 또는 최대 노드가 가장 앞에 위치하지만 내부적으론 정렬 되어있지 않음.

 

---