Heap

Heap

• “우선순위 Queue”를 위해 만들어진 자료구조

우선순위 Queue

• 데이터들이 우선순위를 가지고 있다.
• 우선순위가 높은 데이터가 먼저 나간다.
• 배열,연결리스트,힙으로 구현 가능
  • 힙이 가장 효율적(삽입,삭제 : O(logN))

public static void main(String[] args) {
        
    PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        
    q.offer(200);
    q.offer(50);
    q.offer(93);
    q.offer(7);
    q.offer(80);
        
    System.out.println(q.poll()); // 7
    System.out.println(q.poll()); // 50
    System.out.println(q.poll()); // 80
    System.out.println(q.poll()); // 93
    System.out.println(q.poll()); // 200
 
}

특징

• 우선순위 개념 + Queue
• 완전 이진트리 기반의 자료구조 → 여러값 중 최대값, 최소값을 빠르게 찾아내도록 만들어진 구조
• HeapTree는 중복된 값 허용 (이진트리는 x)
• 반정렬 상태
  • node와 level을 보기 때문에 정렬이 아닌 반정렬이라고 하는 것 같다.

트리

• Root : 부모가 없는 최상단 노드
• Leaf : 자식이 없는 말단 노드

이진 트리

• 각 노드에 최대 두 개의 자식을 갖을 수 있는 트리

이진 탐색 트리

• 모든 노드가 특정 순서를 따르는 속성이 있는 이진 트리

종류

최대 힙

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 부모 노드의 값(key 값) ≥ 자식 노드의 값(key 값)

최소 힙

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• 부모 노드의 값(key 값) ≤ 자식 노드의 값(key 값)

구현

힙을 저장하는 표준적인 자료구조는 배열이다.

구현을 쉽게 하기 위해 배열의 첫번째 인덱스인 0은 사용되지 않는다.

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

(ex. 루트 노드(1)의 오른쪽 노드 번호는 항상 3)

💬 배열?

연결리스트로도 구현이 가능하긴 하지만, 문제는 특정 노드의 '검색', '이동' 과정이 조금 더 번거롭기 때문이다.

배열의 경우는 특정 인덱스에 바로 접근할 수가 있기 때문에 좀 더 효율적이기도 하다.

특징

배열로 구현할 경우(min heap)

• 구현의 용이함을 위해 시작 인덱스(root)는 1 부터 시작한다.
• 각 노드와 대응되는 배열의 인덱스는 ‘불변한다’

성질(부모 노드와 자식 노드 관계)

• 부모 index = (자식 index) / 2
• 왼쪽 자식 index = (부모 index) * 2
• 오른쪽 자식 index = (부모 index) * 2 + 1

ex) index 3 의 왼쪽 자식 노드를 찾고 싶다면 3 × 2를 해주면 된다.
즉 index 6 이 index 3 의 자식 노드라는 것이다.

반대로 index 5의 부모 노드를 찾고 싶다면 5 / 2 를 해주면 된다.(몫만 취함)
그러면 2 이므로 index 2가 index 5의 부모노드라는 것이다.

삽입

• 힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 삽입
• 새로운 노드를 부모 노드들과 교환

최대 힙

“부모 ≤ 자식” 조건으로 swap

최소 힙

“부모 ≥ 자식” 조건으로 swap

1. 가장 마지막 위치에 노드 추가
2. 부모 노드와 비교하여 작은 노드가 상위 레벨에 있도록 swap (완전한 구조가 될때까지 반복)

삭제

• 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다. (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것)
• 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
• 힙을 재구성 (연산 실행)

활용

• 시뮬레이션 시스템
• 작업 스케줄링
• 수치해석 계산