힙(Heap)

처음에 공부했을 때, 그 프로세스의 메모리 구조인 힙을 생각했었다.

틀린 건 아닌데, 카테고리가 자료구조이니깐 자료구조/힙을 생각합시다.

 

이것 또한 면접 대비를 위해 기초 질문, 심화 질문? 점차 확장해간다.

 

힙(Heap) 은 완전 이진 트리 형태를 가지고 잇어야하고, 부모의 값보다 크거나 작아야하는 규칙을 가진 자료구조

그리고 영단어로는 힙은 무엇인가를 차곡차곡 쌓아올린 더미라는 뜻이다.

 

그래서 Max Heap, Min Heap 이 나오게되는데, 목적이 중요하다.

말 그대로 최댓값, 최솟값을 빠르게 찾기위해서 사용된다는 것을 알아두고 규칙을 이해하면 된다.

 

그리고, 찾아보면 단순히 최댓값또는 최솟값을 찾기 위해서라면 항상 완전 이진트리 형태일 필요는 없다고 한다.

--> 아직 더 찾아봐야하는데, 사실 그렇긴 함.

완전 이진 트리의 형태여야하는 이유는 삽입/삭제의 속도 때문이다.

 

Max Heap은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
--> 즉, 루트 노드 (꼭대기)가 최댓값

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

--> 루트 노드(꼭대기)가 최솟값

 

힙에서 삽입/ 삭제 부분은 코드와 같이 포스트 올릴 예정.

--> 어렵지는 않은데, 지금 올리기엔 복잡해진다.

 

힙 정렬, 우선 순위 큐 등을 학습하고 게시글 올릴 예정이다.