힙 (Heap)

• 완전 이진트리 형태로, 최대/최솟값을 빠르게 찾아내는데 유용한 자료구조
• 중복값을 허용
• 부모-자식 간 정렬은 보장, 형제간의 정렬은 보장하지 않는 반 정렬 상태

최소 힙 (Min Heap)

• 루트 노드가 최솟값인 힙

삽입 과정

• 트리의 가장 끝 위치에 데이터를 삽입하고, 부모노드와 key값을 비교하여 작을 경우 보모 노드와 자리를 교체하는 것을 반복한다.

삭제 과정

• 가장 최상위 노드를 반환하며 삭제한다.
• 최상위 노드에 가장 마지막 위치의 노드를 위치시키고, 삽입과 반대의 과정으로 자식노드와 비교하며 자리를 교체한다. (좌, 우 노드와 비교하여 더 작은 값과 자리를 교체한다.)

최대 힙 (Max Heap)

• 루트 노드가 최댓값인 힙

삽입 과정

• 트리의 가장 끝 위치에 데이터 삽입을 하고, 부모노드와 key값을 비교하여 클 경우 부모 노드와 자리를 교체하는 것을 반복한다.

삭제 과정

• 최상위 노드를 반환하며 삭제한다.
• 최상위 노드에 가장 마지막 위치의 노드를 위치시키고, 삽입과 반대의 과정으로 자식 노드와 비교마혀 자리르 ㄹ교체한다. (좌, 우 노드와 비교하여 더 큰 값과 자리를 교체한다.)

우선순위 큐 (Priority Queue)

• 자바에서는 우선순위 큐(Priority Queue)라는 자료구조가 힙을 사용할 수 있다.
• 우선순위 큐는 Queue와 비슷하지만, 선입선출이 아닌 우선순위를 설저앟여 우선순위가 높은 순서대로 poll()한다.

예제

PriorityQueue<Integer> minHeap = new PriorityQueue();
minHeap.add(1)
minHeap.add(5)
minHeap.add(3)
minHeap.add(2)
minHeap.add(4)
while(!heap.isEmpty()) {
	System.out.println(minHeap.poll());
}

###
1
2
3
4
5
###

PriorityQueue<Integer> maxHeap = new PriorityQueue(Collections.reversOrder());
maxHeap.add(1)
maxHeap.add(5)
maxHeap.add(3)
maxHeap.add(2)
maxHeap.add(4)
while(!maxHeap.isEmpty()) {
	System.out.println(heap.poll());
}

###
5
4
3
2
1
###