[알고리즘] 최대 힙 삽입,삭제 JAVA 구현

https://yeoncoding.tistory.com/573

[자료구조] 우선순위 큐(Priority Queue)와 힙(Heap)

 

힙의 개념은 위의 링크에 정리해두었다.

 

아래는 최대힙의 삽입, 삭제를 리스트로 구현한 것이다. 

 

class MaxHeap{
    List<Integer> list;

    public MaxHeap(){
        list = new ArrayList<>(100001);
        list.add(0);
    }

    public void insert(int val){
        // 1. 마지막에 추가
        list.add(val);
        // 2. 부모와 조건 비교, 교환
        int current = list.size()-1;
        int parent = current/2;
        while(true){
            // 1. current 가 root면 탈출
            // 2. 부모, 자식이 조건을 만족하면 탈출
            if(parent == 0 || list.get(parent) >= list.get(current)){
                break;
            }
            // swap
            int tmp = list.get(parent);
            list.set(parent, list.get(current));
            list.set(current, tmp);

            current = parent;
            parent = current/2;

        }
    }
    public int delete(){
        // 1. root 제거
        int top = list.get(1);
        // 2. 마지막 노드를 root로 이동
        list.set(1, list.get(list.size()-1));
        list.remove(list.size()-1);

        // 3. 왼쪽, 오른쪽 중 조건이 안맞는 것을 선택 후 조건에 맞게 swap
        int currentNode = 1;
        while(true){
            int leftNode = currentNode *2;
            int rightNode = currentNode *2+1;

            if(leftNode >= list.size()){ // 말단 노드라면
                break;
            }
            int targetValue = list.get(leftNode);
            int targetNode = leftNode;

            if(rightNode < list.size() && targetValue < list.get(rightNode)){ //오른쪽 노드가 존재하고 왼쪽노드보다 더 크다면
                targetNode = rightNode;
                targetValue = list.get(rightNode);
            }
            if(list.get(currentNode)<targetValue){ // 자식 노드중에 큰 것보다 currentNode가 작으면 교체한다. 
                // swap
                int tmp = list.get(currentNode);
                list.set(currentNode, list.get(targetNode));
                list.set(targetNode, tmp);
                currentNode = targetNode;
            }else break;
        }
        return top;
    }
}