[자료구조 알고리즘] Binary Heaps (Min-Heaps and Max-Heaps)

힙이란?

최대값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된

완전 이진트리를 기본으로 한 자료구조다

최소힙은 작은 값이 항상 가장 위에 노드에 있게해서 트리의 루트에는 가장 작은 값이 오게하는 최소힙이다.

가장 큰값이 맨 위에 오도록하는 구조가 최대힙이다.

• 최소힙에 노드 삽입하기

완전 트리에 맨 끝에 노드를 추가한다.

트리가 컴플리트 바이너리 형태를 잃지 않도록 마지막 레벨의 왼쪽부터 채워나간다.

다음 스텝은 자신의 부모 노드와 비교해서 자신이 값이 작으면 부모 노드랑 자리를 바꾼다.

부모 노드가 자기보다 작을 때 까지 반복한다.

완전 이진 트리에서 이루어지니까 한번 돌 때 마다 o(logn)의 시간 복잡도를 가진다.

• 최소힙에서 노드 꺼내오기

최소힙에서 작은 값은 루트에있으니까 어렵지 않다. 루트의 값을 빼온 다음에는 완전 이진 트리 맨 마지막을 루트 자리로 채운다. 자식 노드 두개를 비교해서 트리의 맨 꼭 대기로 보낸다. 맨 마지막 잎사귀에 가장 큰 값이 들어가면 종료한다.

 

힙은 객체가 저장되는 메모리 공간이다. 콜 스택의 요소인 실행 컨텍스트는 힙에 저장된 객체를 참조한다. 메모리에 값을 저장하려면 먼저 값을 저장할 메모리 공간의 크기를 결정해야한다. 객체는 원시 값과는 달리 크기가 정해져 있지 않으므로 할당해야 할 메모리 공간의 크기를 런타임에 결정(동적 할당) 해야한다. 따라서 객치게 저장되는 메모리 공간인 힙은 구조화 되어 있지 않다는 특징이있다.