📍 정의 및 특징
- 완전 이진 트리의 일종
- 반정렬 상태 (완전 정렬 X)
- 중복값 허용
- 시간 복잡도 : O(logN)
- 종류 : 최대 힙 (부모 노드가 가장 큰) / 최소 힙 (부모 노드가 가장 작은)
- 구현 : 우선순위 큐
#완전이진트리 #우선순위큐
📍 필요 변수
✔ 우선순위 큐
✔ 배열
📍 실행 과정
- 부모 노드가 N (N ≥ 1)이면, 자식 노드는 *2, *2 + 1
- 자식 노드가 N이면, 부모 노드는 N/2
➕ 예제
[백준/JAVA] 1927번: 최소 힙
🔺 문제 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(
bono039.tistory.com
[백준/JAVA] 11279번: 최대 힙
🔺 문제 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(
bono039.tistory.com
(참고)
[자료구조/Java] 힙(Heap) 구현
시간이 지나면 자꾸 까먹는다.. 그래서 다시 정리해봐야겠다 자료구조의 핵심 중 하나인 힙(Heap)에 대해 알아보자 힙(Heap) 완전 이진트리의 일종이다. 반정렬 상태(완전히 정렬된 상태가 아님)이
kim6394.tistory.com
우선순위 큐 사용자 기준 정렬
목차 1. Comparator 이용 PriorityQueue pq = new PriorityQueue(Collections.reverseOrder()); - default : 오름차순 2. Comparator 구현 PriorityQueue pq = new PriorityQueue(new Comparator() { @Override public int compare(Integer o1, Integer o2) { retur
bono039.tistory.com
'코테 > 알고리즘' 카테고리의 다른 글
| 그리디 (0) | 2023.09.04 |
|---|---|
| 백트래킹 (0) | 2023.08.24 |
| 슬라이딩 윈도우 (0) | 2023.08.01 |
| LIS (최장 증가 부분 수열) (0) | 2023.07.19 |
| LCS (최장 공통 부분 수열) (0) | 2023.07.06 |
