Heap

힙이란, 특정한 규칙을 만족하도록 구성된 이진 트리이다.

1. 힙의 대소관계 규칙
   부모 노드가 항상 자식 노드보다 크거나 같다 (자식 노드 index = 부모 노드 index / 2 (+1))
   즉, 가장 큰 원소는 항상 힙의 루트에 있다.
   
   
2. 힙의 모양 규칙
   마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다
   마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다

이러한 특성 덕분에 힙은 최대 원소를 빠르게 찾을 수 있다

6개의 정수를 저장하는 힙의 예

16 삽입

삭제

* 대소관계 규칙을 반대로 적용하면 최소 원소를 빠르게 찾을 수 있다

연산을 편하게 하기 위해서 0번에는 최소 혹은 최대값을 넣어주고 1번부터 값을 채운다

    public abstract class Heap {
        final List<Integer> heap = new ArrayList<>();

        Heap(int root) {
            heap.add(root);
        }

        void insert(int val) {
            heap.add(val);
            int pos = heap.size() - 1;

            while (pos > 1 && !isLegal(pos, pos / 2)) {
                swapMem(pos, pos / 2);
                pos /= 2;
            }
        }

        int delete() {
            if (heap.size() <= 1) return -1;

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

            int pos = 1;
            while (2 * pos < heap.size()) {
                int nextPos = getChildPos(pos);

                if (isLegal(nextPos, pos)) break;

                swapMem(nextPos, pos);
                pos = nextPos;
            }
            return deleteItem;
        }

        abstract int getChildPos(int pos);

        abstract boolean isLegal(int child, int parent);

        private void swapMem(int a, int b) {
            int tmp = heap.get(a);
            heap.set(a, heap.get(b));
            heap.set(b, tmp);
        }
    }

    public class minHeap extends Heap {
        public minHeap() {
            super(0);
        }

        @Override
        boolean isLegal(int child, int parent) {
            return heap.get(child) > heap.get(parent);
        }

        @Override
        int getChildPos(int pos) {
            int nextPos = 2 * pos;
            if (nextPos + 1 < heap.size() && heap.get(nextPos) > heap.get(nextPos + 1)) {
                nextPos += 1;
            }
            return nextPos;
        }
    }

    public class maxHeap extends Heap {
        maxHeap() {
            super(999999999);
        }

        @Override
        boolean isLegal(int child, int parent) {
            return heap.get(child) < heap.get(parent);
        }

        @Override
        int getChildPos(int pos) {
            int nextPos = 2 * pos;
            if (nextPos + 1 < heap.size() && heap.get(nextPos) < heap.get(nextPos + 1)) {
                nextPos += 1;
            }
            return nextPos;
        }
    }