힙(Heap)

힙 ( Heap )

힙이란 완전이진트리의 형태로 만들어진 자료구조 이다.

*이진트리란 컴퓨터 응용에서 가장 많이 활용되는 트리구조이다.

---

힙의 종류

- 최대 힙 : ( 완전 이진 트리 ) + ( 부모 노드 > 자식 노드 )

최대 힙은 완전 이진 트리이면서 부모 노드가 자식 노드보다 큰 트리를 말한다.

- 최소 힙 : ( 완전 이진 트리 ) + ( 부모 노드 < 자식 노드 )

최소 힙은 완전 이진 트리이면서 부모 노드가 자식 노드보다 작은 크리를 말한다.

*보통 힙이라고 하면 일반적으로 최대 힙을 의미한다.

---

힙의 활용

힙은 최댓값 혹은 최솟값을 빠르게 찾아내기 유리한 자료구조이다.

1. 우선순위 큐를 구현할 때 쓰이기도 한다.

2. 허프만 코드를 구현할 때도 쓰이기도 한다.

3. 힙 정렬을 구현 할 때도 쓰인다.

* 허프만 코드 : 데이터를 효율적으로 압축하는데 사용하는 방법 ( 탐욕 알고리즘 중 하나 ) 

---

힙 삽입

힙을 만들기 위해서는 값 삽입 > 힙 구조 변경 > 값 삽입 > 힙 구조 변경 .... 반복

https://todaycode.tistory.com/56

힙(Heap) 이란?

---

힙 코드

public void init()  throws IOException{
	PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    System.out.println("최소 힙");
    runHeapTest(minHeap);

	
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    System.out.println("최대 힙");
    runHeapTest(maxHeap);
}
	
private void runHeapTest(PriorityQueue<Integer> heap) {
	heap.add(1);
	heap.add(8);
	heap.add(5);
	heap.add(2);
	heap.add(3);
	while(!heap.isEmpty()) {
    	System.out.println(heap.poll());
    }
}

 

---

우선순위 큐 PriorityQueue 사용하기 (heap)