Heap 자료구조에 대해 알아보자(java..)

1. 힙(Heap)

• 우선순위 큐를 위해 고안되었다.
• 완전이진트리 형태의 자료구조이다.
• 부모 노드의 값이 자식노드의 값보다 항상 크거나 같거나 작거나 같다.(반 정렬 상태)

1-1. 힙의 종류

1-1-1. 최대 힙 (Max Heap)

부모 노드의 값이 자식노드의 값보다 크거나 같다.

1-1-2. 최소 힙(Min Heap)

부모 노드의 값이 자식 노드의 값보다 작거나 같다.

1-2. 힙의 동작 방식

1-2-1. 데이터 삽입

데이터 삽입과정

 

1. 최하단 노드에 값을 추가한다.

2. 추가할 경우 왼쪽노드를 우선으로 한다.

 

부모보다 큰 값이 들어온다면

3. 최하단 노드의 왼쪽에 값을 추가하고 부모와 비교해서 더 크다면 부모와 바꿔준다.

1-2-2. 데이터 삭제

데이터 삭제과정

 

1. pop 하면 앞에 값이 나가게 되고 최하단의 값이 들어간다.

 

 

2. 자식노드 중 더 큰 값 (9와 6중에서는 9~)과 바꿔준다.

 

1-3. java에서의 heap사용(우선순위 큐)

위에서 언급했던 것과 같이 우선순위 큐를 사용하기 위해 고안되었다.

위에서 설명한 것과 같이 코드를 작성해 보면

public static void main(String[] args) {
        //오름차순으로 선언
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());
        
        heap.add(10);
        heap.add(8);
        heap.add(6);
        heap.forEach(e -> System.out.print(e + " "));
        System.out.println();
        heap.add(9);
        heap.add(4);
        heap.forEach(e -> System.out.print(e + " "));
        System.out.println();
        heap.poll();
        heap.forEach(e -> System.out.print(e + " "));
    }
    
    //결과
    /*
   	10 8 6 
	10 9 6 8 4 
	9 8 6 4
    */