[자료구조] 힙(Heep) & 우선순위 큐

힙(Heep)

• 최댓값, 최솟값을 빠르게 찾기 위해 고안된 자료형으로 우선순위 큐를 위해 만들어졌다.

• 완전 이진 트리의 일종으로, 각 노드의 키값이 그 자식의 키 값보다 작지않거나(최대 힙), 크지 않은(최소 힙) 완전 이진 트리이다.

  • 완전이진트리는 중복을 허용하지 않지만 힙은 허용한다.

우선순위 큐

• 우선순위가 있는 큐

• 가장 우선순위가 높은 데이터가 먼저 나간다.

• 배열, 연결리스트 힙 으로 구현이 가능하다.

  • 힙으로 구현하는 것이 가장 효율적이다.

    자료구조	삽입	삭제
    정렬된 배열 / 순서 없는 배열	O(n) / O(1)	O(1) / O(n)
    정렬된 연결 리스트 / 순서 없는 연결리스트	O(n) / O(1)	O(1) / O(n)
    힙	O(logn)	O(logn)

힙(Heap)

• 최대 힙(Max heap)

  • 부모 노드의 키 값이 그 자식 노드의 키 값보다 큰 힙

• 최소 힙(Min heap)

  • 부모 노드의 키 값이 그 자식 노드의 키 값보다 작은 힙

• 특징

  • 힙에서의 부모 자식 관계

    • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2+1

    • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2

    • 부모의 인덱스 = (자식의 인덱스) / 2

힙(최소 힙) 삽입

• 힙에 삽입을 하면 먼저 제일 마지막 노드에 삽입한다.

• 힙의 특징에 맞게(최소 힙인지 최대 힙인지) 부모와 자식을 교환한다.

힙의 삭제

• 힙의 삭제는 항상 루트에서만 해야한다.

• 루트에서 삭제를 한 뒤 다음 루트가 될 노드를 정한다. (정하는 방법은 다음과 같다.)

  1. 루트 노드를 삭제한다.

  2. 트리의 레벨 중 가장 마지막 노드를 루트로 옮긴다.

  3. 힙의 종류에 맞게(최대힙, 최소힙) 루트로 옮겨진 노드와 자식 노드를 비교하면서 힙 조건을 검사한다.

  4. 만약 힙의 종류의 조건에 만족하지 않으면 교환한다.

  5. 힙의 종류의 조건에 만족할 때까지 반복한다.

자바 우선선위 큐

• 자바에서 우선순위 큐(PriorityQueue)를 제공한다.

PriorityQueue priority = new PriorityQueue<>(Collections.reverseOrder());

 

• reverseOrder()는 내림차순으로 정렬해주는 것이다.
• 우선순위 큐에 {3,9,7,1,5}를 넣었을 때 내림차순인 {1,3,5,7,9}가 나올줄 알았는데 결과는 {9,5,7,1,3}이다.
• 이렇게 되는 이유는 바로 우선순위 큐가 힙으로 구현되었기 때문이다.
• 이럴 때는 Comparator를 이용해서 해결해야한다.

즉, 자바에서 우선순위 큐는 최댓값, 최솟값이 필요할 때 사용한다!!!