비선형 자료구조 - Heap

힙 (Heap)

완전 이진 트리 형태

• 중복 값 허용
• 반 정렬 상태

최솟값 또는 최댓값을 빠르게 찾아내는데 유용한 자료구조

• 최소 힙, 최대 힙

최소 힙 (Min Heap)

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

최대 힙 (Max Heap)

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

최소 힙 삽입 및 삭제

삽입

트리의 가장 끝 위치에 데이터 삽입
부모 노드와 키 비교한 후 작을 경우 부모 자리와 교체(반복)

삭제

최상위 노드 반환 및 삭제
가장 마지막 위치의 노드를 최상위 노드로 위치 시킴
자식 노드 중 작은 값과 비교 후 부모 노드가 더 크면 자리 교체 (반복)

ArrayList로 최소 힙 구현

생성자 생성

ArrayList<Integer> heap;

    public MinHeap(){
        this.heap = new ArrayList<>();
        this.heap.add(0);
    }

Insert

 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);
            heap.set(cur / 2, data);
            heap.set(cur, parentVal);

            cur /= 2;
        } 
    }

Delete

 public Integer delete(){
        if (heap.size() == 1){
            System.out.println("Heap is Empty!");
            return null;
        }

        int target = heap.get(1);
        heap.set(1, heap.get(heap.size() -1 ));
        heap.remove(heap.size() - 1);

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

            if (rightIdx < heap.size()){
                targetIdx = heap.get(leftIdx) < heap.get(rightIdx) ? leftIdx : rightIdx;
            }else if (leftIdx < heap.size()){
                targetIdx = cur * 2;
            }else {
                break;
            }

            if (heap.get(cur) < heap.get(targetIdx)){
                break;
            }else{
                int parentVal = heap.get(cur);
                heap.set(cur, heap.get(targetIdx));
                heap.set(targetIdx, parentVal);
                cur = targetIdx;
            }
        }
        return target;
    }

Print

public void printTree(){
        for (int i = 1; i < this.heap.size(); i++) {
            System.out.print(this.heap.get(i) + " ");
        }
        System.out.println();
    }

손 노트 정리