힙

 

힙 => 완전 이진 트리 형태(마지막 level빼고 모든 노드가 채워져있으면 됨)

 - 중복 값 허용

 - 반 정렬 상태(형제 사이의 크고 작음은 보장하지 않음)

 - 최소값 또는 최대값을 빠르게 찾아내는 데 유용한 자료구조

 

최소힙 <-> 최대힙 서로반대

부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태

최소힙

 

최소힙 삽입 

트리의 가장끝에 삽입 후 부모노드와 비교해 작을경우 부모노드와 교체 

오른쪽(삽입 후)

 

최소힙 삭제 

최상위 노드 삭제 후 가장 마지막 위치의 노드와 교체  자식 노드중 더 작은 값이 있다면 자리 교체 

 

 

구현 -> ArrayList활용

class MinHeap{
    ArrayList<Integer> heap;


    public MinHeap(){
        heap = new ArrayList<>();
        heap.add(0);//인덱스 1부터 시작할 수 있게 더미 데이터 삽입
    }

    public void insert(int data){
        heap.add(data);

        int cur = heap.size()-1; //마지막 데이터의 위치

        while (cur > 1 && heap.get(cur / 2) > heap.get(cur)){// 부모와 자식을 비교
            int parentVal = heap.get(cur / 2);// 현재 위치에서 나누기 2는 부모의 위치
            heap.set(cur / 2 , data);//부모의 값과 자식의 값을 변경
            heap.set(cur, parentVal);//동일

            cur /=2;//위로 계속 올라가면서 탐색
        }

    }

    public int delete(){
        int min = heap.get(1);
        heap.set(1, heap.get(heap.size()-1));

        heap.remove(heap.size()-1);

        int current = 1;
        while (true){
            int leftIdx = current * 2;
            int rightIdx = current * 2 + 1;
            int targetIdx = -1;

            if(rightIdx < heap.size()){// 힙 갯수 안에 있다면 왼쪽 오른쪽 모두 존재하는것임으로
                targetIdx = heap.get(leftIdx) < heap.get(rightIdx) ? leftIdx : rightIdx;// 둘중 비교해서 작은 곳으로 이동
            }else if(leftIdx < heap.size()){//왼쪽만 존재
                targetIdx = leftIdx;
            }else{
                break;
            }

            if(heap.get(current) < heap.get(targetIdx)){// 부모노드가 더작음으로 변경 x
                break;
            }else {
                int parentVal = heap.get(current);
                heap.set(current, heap.get(targetIdx));
                heap.set(targetIdx, parentVal);
                current = targetIdx;// 변경해준 idx부터 다시 비교해야함으로 current를 targetIdx로 이동
            }
        }


        return min;
    }