[자료구조] 힙 개념과 JAVA로 구현

항상 문제를 풀때마다 힙(heap)에 대한 개념이 많이 헷갈려서 포스팅한다. 다른 분의 블로그에 매우 잘 정리된 포스팅을 가져와 정리해서 쓴 글이다.

힙(Heap)

힙은 이진트리의 일종이다.
반정렬 상태(정렬된 상태가 아니다)이며, 완전이진트리와는 다르게 중복값이 허용된다.
삽입/삭제는 트리 구조이기 때문에 O(logN)이므로 매우 빠르다.

보통 우선순위 큐가 힙으로 많이 구현되는데, 배열과 리스트보다 효율적이다.

힙은 최대힙, 최소힙으로 나뉘어진다. 최대힙은 부모노드가 자식노드보다 큼 이라는 특징을 가지고 최소힙은 부모노드가 자식노드보다 작음 이라는 특징을 가지고 있다. 이러한 특징으로 힙에 값을 넣게 되면 최소힙에서는 최소값 순으로, 최대힙에서는 최대값 순으로 값을 얻을수 있다.

힙 자료구조는 보통 배열을 사용하며, 0번째 인덱스는 계산을 편하게 하기위해 사용하지 않는다. 부모노드의 인덱스가 1이 되어진다

1번째 인덱스부터 시작하며, 해당 인덱스의 자식 노드는 각각 1x2, 1x2 +1로 나타낼수 있다. 결국 모든 부모와 자식 간의 인덱스 관계는 부모:N, 왼쪽자식:2N, 오른쪽자식: 2N+1 를 가진다.

우선순위 큐를 이용해서 문제를 풀어야 할때 B형 시험처럼 라이브러리 사용이 불가능할 때 힙을 구현해야 한다.

구현 전에 힙의 연산 전개가 어떻게 진행되는지 정리를 해보자

최소힙 삽입연산 전개

[insert 메소드]
//heap배열의 맨 뒤에 값을 삽입
//삽입한 값의 인덱스 저장
//삽입한 값의 인덱스가 1보다 크며 부모노드가 있다는 뜻
//while(삽입한 값의 인덱스가 1보다 크고 새로 삽입한 값이 부모노드보다 작으면 )
//서로 위치 바꿈
//삽입한 값의 인덱스 /= 2 저장(노드의 위치가 한칸 올라갔기 때문
//부모 노드가 더 작을때 까지 반복

[delete 메소드]
//heap.size가 비어있으면 리턴
//부모 노드값 저장
//부모 노드의 맨 마지막 값 저장
//맨 마지막 값 삭제 -> 사이즈가 1 줄음
//pos값 1로 선언(첫 부모의 인덱스)
//while((pos*2)<heap.size()) -> pos*2는 자식의 인덱스, 자식의 인덱스보다 사이즈가 작다는 것은 자식이 없다는 뜻
//min = 왼쪽 자식 노드 값
//minPos = 왼쪽 자식 노드 인덱스
//오른쪽 자식 노드가 있는지 여부 확인, 오른쪽 노드가 더 작으면 min,minPos를 오른쪽 노드로 갱신
//min이 부모보다 더 크면 바꿀 필요 없으므로 종료
//부모와 자식 노드 교환

JAVA로 힙을 구현한 코드는 아래와 같다.

최소 힙

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;
        }

    }

최대 힙

class MaxHeap{
        private ArrayList<Integer> heap;

        public MaxHeap() {
            heap = new ArrayList<Integer>();
            heap.add(0); //첫번째 인덱스는 사용하지 않음
        }

        //삽입
        public void insert(int val) {
            //맨 마지막 위치에 삽입
            heap.add(val);

            int  p = heap.size()-1; //새로 넣은 노드의 인덱스 위치 정보
            //루트까지 이동 자식이 더 크면 교환
            while(p>1 && heap.get(p)> heap.get(p/2)) {
                int tmp = heap.get(p/2);
                heap.set(p/2, heap.get(p));
                heap.set(p, tmp);

                p /= 2;
            }
        }
        //삭제
        public int delete() {
            //힙 이 비어있으면 0리턴
            if(heap.size()-1 < 1) {
                return 0;
            }

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

            //맨 마지막 자식 루트에 넣고 마지막 값 삭제
            heap.set(1,heap.get(heap.size()-1));
            heap.remove(heap.size()-1);

            //루트에 새로 넣은 노드의 인덱스 정보
            int pos = 1;
            while((pos*2)<heap.size()) {

                int max = heap.get(pos*2);
                int maxPos = pos*2;

                //오른쪽 자식이 존재하고 오른쪽 자식이 왼쪽 자식보다 클때 바꿀 자식 오른쪽으로 설정
                if((pos*2 +1)<heap.size() && max < heap.get(pos*2+1)) {
                    max = heap.get(pos*2+1);
                    maxPos = pos*2+1;
                }

                //부모가 더 크면 끝
                if(heap.get(pos) > max){
                    break;
                }

                //자식이 더 크면 교환
                int tmp = heap.get(pos);
                heap.set(pos, max);
                heap.set(maxPos, tmp);
                pos = maxPos;
            }
            return deleteitem;
        }
    }

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

https://www.acmicpc.net/problem/11279

11279번: 최대 힙