[알고리즘] 힙(Heap)

[힙(Heap)]

1. Heap이란?

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
• 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조로 반정렬 상태(느슨한 정렬 상태)이다.
• 힙 트리는 중복된 값을 허용한다. (이진 탐색 트리는 중복값 허용X)

 

※ 완전 이진 트리의 특징

완전이진트리

1) 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다. 

2) 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

3) 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.

 

※ 반정렬 상태

트리 구조를 배열에 저장한 것이므로 배열로만 보았을 때는 완전히 정렬된 상태로 보이지는 않는다는 것을 의미.

 

2. 힙의 종류

1) 최대 힙(max heap)

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

 

2) 최소 힙(min heap)

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

 

최대힙과 최소힙

3. 힙의 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 구현을 쉽게 하기 위하여 배열의 첫번째 인덱스인 0은 사용되지않는다.
• 특정 위치의 노드번호는 새로운 노드가 추가되어도 변하지 않는다.
  예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
  • 왼쪽 자식의 인덱스 = (부모의 인덱스)*2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스)*2+1
  • 부모의 인덱스 = (자식의 인덱스)/2
  • 힙에서의 부모 노드와 자식 노드의 관계

 

4. 힙의 삽입

• 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 이이서 삽입한다.
• 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

예시)

※ 같은 레벨의 자식노드들 끼리의 크기는 중요하지 않다.

 

5. 힙의 삭제

1) 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다.(최소 힙에서는 최소값인 루트노드가 삭제

2) 삭제된 루트 노드에는 마지막 노드를 가져온다.

3) 힙을 재구성한다. 

예시)

 

6. JAVA Priority Queue 사용법

1) Priority Queue 선언

import java.util.PriorityQueue; //import

//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 
//String형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

 

2) Priority Queue 값 추가

priorityQueue.add(1);     // priorityQueue 값 1 추가
priorityQueue.add(2);     // priorityQueue 값 2 추가
priorityQueue.offer(3);   // priorityQueue 값 3 추가

자바의 우선순위 큐에 값을 추가하고 싶다면 add(value) 또는 offer(value)라는 메서드를 활용하면 된다.

• add() : 삽입에 성공하면 true를 반환, 큐가 꽉 찬 경우 IllegalStateException을 발생
• offer() : 값 추가 성공 시에 true를 반환, 값 추가 실패 시 false를 반환

 

3) Priority Queue 값 삭제

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
priorityQueue.clear();      // priorityQueue에 초기화

• poll() : 큐가 비어 있을 경우 null 반환
• remove() : 큐가 비어 있는 경우 NoSuchElementException 에러 발생
• clear() : 큐 비우기

4) Priority Queue에서 우선순위가 가장 높은 값 출력

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();//int형 priorityQueue 선언
priorityQueue.offer(2);     // priorityQueue에 값 2 추가
priorityQueue.offer(1);     // priorityQueue에 값 1 추가
priorityQueue.offer(3);     // priorityQueue에 값 3 추가
priorityQueue.peek();       // priorityQueue에 첫번째 값 참조 = 1

 

- 프로그래머스 Heap 관련 문제 ( Level2 / 더 맵게 ) 

프로그래머스

 

- 참고 지식

※ 자료구조 heap과 메모리영역의 heap의 관련성?

과거에 일부 개발자들이 가용 메모리를 heap이라 부르기 시작한 것 같고, 특별한 이유는 없는 것으로 보임.

결국 stack 메모리는 stack 자료구조로 된 것이 맞지만,

heap 메모리는 heap(우선순위큐) 자료구조와 아무런 연관성이 없다고 볼 수 있다.

 

- 출처

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

https://velog.io/@yanghl98/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Heap%ED%9E%99-%EA%B0%9C%EB%85%90-%EC%A2%85%EB%A5%98-%ED%99%9C%EC%9A%A9-%EC%98%88%EC%8B%9C-%EA%B5%AC%ED%98%84

https://coding-factory.tistory.com/603