컴퓨터의 힙(Heap)

때는 대학생, 한참 이력서를 넣고 있던 시절, 전화면접이 있었다.

전화 면접관 : 질문 중 하나가 자료구조의 힙에 대해 설명해 보시겠어요?
나 : ?????? 힙은 메모리를 말하는게 아닌가요???????
전화 면접관 : .......(침묵)
나 : ................. (속으로 울고있음)

면접 이후, 자료구조 힙에 대해 공부하였고, 현재 자료구조 서적에서 다시금 보이길래 메모리의 힙과 자료구조 힙에 대한 설명을 담는다.

메모리 힙(Heap)

프로그램이 실행되면 아래 그림과 같이 4개의 메모리 영역을 가지게 된다.

이중 Heap 영역은 사용자가 동적할당을 할 경우 메모리에 저장된다.

C언어에서는 malloc, java에서는 new 키워드로 Heap 영역에 메모리를 할당할 수 있다. 

Heap 메모리의 해제는 C에서는 free 함수로 해제하며, java에서는 JVM에서 가비지 컬렉터가 지우는 시점에 해제된다.

자료구조의 힙(Heap)

힙은 완전 이진 트리이다. 최소 값 혹은 최대 값을 찾아내는 연산에 적합하다.

힙에는 최소 힙과 최대 힙이 있다. 최대 힙은 루트노드로 갈수록 값이 커지며, 최소 힙은 루트노드로 갈수록 값이 작아진다. ( 아래 그림 참조)

일반 이진 트리를 구현할때는 연결 리스트(링크드 리스트)를 많이 사용하는데, 힙은 배열로 구현하는 것이 원칙처럼 여겨진다. 이유는, 힙에서 데이터를 추가하면, 노드를 연결하고 데이터 값에 따른 노드의 위치조정을 해야한다. 반면 배열로 구현할 경우, 배열의 인덱스를 통해 훨씬 쉽게 구현이 되기 때문이다.

힙에서 데이터 추가 과정에 대해 상세히 설명하려면.. ppt로 그림을 여러번 그려야 되기 때문에 과감히 생략하고.. 다른 블로그를 찾아주세염 ㅎ.ㅎ........