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
- type
- rendering
- javascript
- refactoring
- 자바스크립트문법
- 렌더링
- 마틴파울러
- js
- 2판
- 타입
- 브라우저
- 도서
- 엘리
- 책
- TypeScript
- basic
- 리팩터링
- 자료구조
- ES5
- React
- 리뷰
- syntax
- 리액트
- 문법
- 기본
- 리팩토링
- 자바스크립트
- 개정판
- 클린코드
- 개발자
Archives
- Today
- Total
Santos의 개발블로그
힙(Heap) 본문
힙(Heap) 특징
1. 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다.
2. 여러개의 값들 중에서 최대값이나 최소값을 빠르게 찾아내도록 만들어진 자료구조이다.
3. 힙은 반 정렬 상태를 유지한다.
4. 힙 트리는 중복 값을 허용한다.
우선순위 큐
1. 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나가는 구조
2. CPU 작업 스케쥴링, 시뮬레이션 시스템에서 사용
3. 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능한데, 힙으로 구현하는게 가장 효율적.
힙 종류
1. 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
2. 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
힙 구현 특징
1. 힙을 저장하는 표준적인 자료구조는 배열이다.
2. 구현을 쉽게 하기 위해 배열의 첫번째 인덱스 0은 사용하지 않는다.
예제 - 최대 힙
< 참고자료 >
[도서] 자료구조 - 정광식 지음-
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
<Data structures> chapter 7, 힙(Heap) end
'CS(Computer science) > 자료구조&알고리즘' 카테고리의 다른 글
이진검색트리(BST) (0) | 2020.01.02 |
---|---|
정렬(Sort) (0) | 2020.01.01 |
그래프(Graph) (0) | 2020.01.01 |
Hash(해시) (0) | 2020.01.01 |
Stack vs Queue (0) | 2020.01.01 |
Comments