처음에 공부했을 때, 그 프로세스의 메모리 구조인 힙을 생각했었다.
틀린 건 아닌데, 카테고리가 자료구조이니깐 자료구조/힙을 생각합시다.
이것 또한 면접 대비를 위해 기초 질문, 심화 질문? 점차 확장해간다.
힙(Heap) 은 완전 이진 트리 형태를 가지고 잇어야하고, 부모의 값보다 크거나 작아야하는 규칙을 가진 자료구조
그리고 영단어로는 힙은 무엇인가를 차곡차곡 쌓아올린 더미라는 뜻이다.
그래서 Max Heap, Min Heap 이 나오게되는데, 목적이 중요하다.
말 그대로 최댓값, 최솟값을 빠르게 찾기위해서 사용된다는 것을 알아두고 규칙을 이해하면 된다.
그리고, 찾아보면 단순히 최댓값또는 최솟값을 찾기 위해서라면 항상 완전 이진트리 형태일 필요는 없다고 한다.
--> 아직 더 찾아봐야하는데, 사실 그렇긴 함.
완전 이진 트리의 형태여야하는 이유는 삽입/삭제의 속도 때문이다.
Max Heap은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
--> 즉, 루트 노드 (꼭대기)가 최댓값
Min Heap은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
--> 루트 노드(꼭대기)가 최솟값
힙에서 삽입/ 삭제 부분은 코드와 같이 포스트 올릴 예정.
--> 어렵지는 않은데, 지금 올리기엔 복잡해진다.
힙 정렬, 우선 순위 큐 등을 학습하고 게시글 올릴 예정이다.
'개발 > 자료구조' 카테고리의 다른 글
큐(Queue) (0) | 2019.06.20 |
---|---|
스택(Stack) (0) | 2019.06.20 |
스택과 큐 (0) | 2019.06.04 |
배열과 연결리스트 (0) | 2019.06.04 |
트리 (0) | 2019.05.18 |