Heap 자료구조의 기본구조

힙 자료구조는 완전 이진 트리를 기초로 하는 자료구조이다.
완전 이진트리는 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리를 말한다.

• 최대 힙(max heap)
  부모 노드 값이 자식 노드의 값보다 크거나 같다.
  루트 값은 저장된 원소 중 가장크다.

• 최소 힙(min heap)
  부모 노드 값이 자식 노드의 값보다 작거나 같다.
  루트 값은 저장된 원소 중 가장작다.

자바에서 Min Heap을 사용하는 방법

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

    }

자바에서 Max Heap을 사용하는 방법

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://go-coding.tistory.com/25