Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 스프링 부트
- 트랜잭션 락
- Java
- DTO
- Entity
- OOP
- 스네이크 케이스
- 파스칼 케이스
- 스터디
- 테스트 코드
- @Version
- jvm
- 자료구조
- springDataJpa
- 마이크로서비스 아키텍처
- 자바
- Repository 테스트
- 비링크
- @Query
- Service 테스트
- Array
- 디자인 패턴
- 원시 자료형
- 배타락
- 낙관락
- 배열
- do...while
- Controller 테스트
- 비즈니스 로직
- 공유락
Archives
- Today
- Total
menuhwang
[자료구조] 힙(Heap) 본문
힙(Heap)
특징
- 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
- 최댓값이나 최솟값을 빠르게 찾아낼 수 있는 자료구조
- 반정렬 상태
- 힙 트리에서는 중복된 값을 허용.
구조


종류
최소 힙
부모 노드의 값이 자식 노드의 값보다 작거나 같은 이진트리.
최대 힙
부모 노드의 값이 자식 노드의 값보다 크거나 같은 이진트리.
동작 원리
최소 힙을 예시로 설명합니다.
노드 추가 O(logN)
1. 가장 마지막 위치에 노드를 추가

2. 부모 노드와 비교하여 작은 노드가 상위 레벨에 있도록 swap! (완전한 구조가 될 때까지 반복)

poll 최솟값 추출 (root 노드 추출) O(logN)
1. 루트 노드 제거

2. 비어있는 루트 노드에 마지막 노드 이동


3. 자식 노드 중 작은 노드와 swap (완전한 구조가 될때까지 반복)

사용 (자바)
선언 - PriorityQueue
public class Heap {
public static void main(String[] args) {
Queue<Integer> queue = new PriorityQueue<>();
}
}
추가 - offer
public class Heap {
public static void main(String[] args) {
Queue<Integer> queue = new PriorityQueue<>();
queue.offer(7);
queue.offer(3);
queue.offer(5);
queue.offer(4);
queue.offer(6);
System.out.println(queue); // [3, 4, 5, 7, 6]
/*
* 3
* 4 5
* 7 6
*/
}
}
값을 추가하면 기본적으로 오름차순으로 정렬되는 것을 알 수 있다.
배열로 출력된 결과를 보면 상위 레벨의 왼쪽 노드부터 차례대로 출력되는 것을 확인할 수 있다.
삭제 - poll
public class Heap {
public static void main(String[] args) {
Queue<Integer> queue = new PriorityQueue<>();
queue.offer(7);
queue.offer(3);
queue.offer(5);
queue.offer(4);
queue.offer(6);
System.out.println(queue.poll()); // 3
System.out.println(queue); // [4, 6, 5, 7]
/*
* 4
* 6 5
* 7
*/
}
}
내림차순 정렬
public class Heap {
public static void main(String[] args) {
Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
queue.offer(7);
queue.offer(3);
queue.offer(5);
queue.offer(4);
queue.offer(6);
System.out.println(queue); // [7, 6, 5, 3, 4]
/*
* 7
* 6 5
* 3 4
*/
}
}
PriorityQueue 생성자 인자로 Comparator를 전달하여 정렬 기준을 설정해줄 수 있다.
내림차순 정렬 람다형
public class Heap {
public static void main(String[] args) {
Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
// ...
}
}
'자료구조' 카테고리의 다른 글
[자료구조] 트리, 이진 트리, 이진 탐색 트리 (0) | 2022.11.21 |
---|---|
[자료구조] 스택(Stack), 큐(Queue) (2) | 2022.11.08 |
[자료구조] 배열(Array), 리스트(List) (0) | 2022.11.08 |