[Data Structure] Heap(힙)

 

힙

• 힙은 항상 완전 이진 트리의 형태를 유지한다
• 모든 레벨이 완전히 채워져 있어야 하며, 마지막 레벨은 왼쪽에서 오른쪽으로 순차적으로 채워진다

힙 속성

최대 힙(Max Heap)

• 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같다
• 루트 노드에 트리의 최대 값이 저장된다

최소 힙(Min Heap)

• 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같다
• 루트 노드에 트리의 최소 값이 저장된다

힙은 동일한 값을 가지는 노드를 허용한다

삽입, 삭제 연산에 평균 및 최악의 경우 모두 O(log n)의 시간 복잡도를 가진다

 

주요 연산

삽입

• 새로운 값은 트리의 마지막 자리에 추가된다 
• 이후 부모 노드와 비교하여 속성이 만족될 때까지 상향 조정(Bubble Up)을 한다

최대 값 또는 최소 값 조회

• 루트 노드를 조회하여 최대 값 또는 최소 값을 얻는다
• O(1)의 시간 복잡도를 가진다

삭제

• 힙에서 루트 노드를 제거한다, 제거 후에 트리 마지막 자리 노드를 루트로 가져오고 자식들과 비교하여 하향 조정(Bubble Dow)을 한다

힙정렬

• 데이터를 힙에 삽입 후 하나씩 꺼내서 정렬된 리스트를 얻는다
• 최대 힙의 경우 내림차순 정렬
• 최소 힙의 경우 오름차순 정렬
• 데이터를 꺼내는 것은 삭제와 같은 의미 데이터를 꺼낸 후 하향조정하여 속성을 복구하고 다시 값을 꺼낸다

 

장점

• 빠른 최대값 또는 최소값 추출
• 효율적인 삽입과 삭제

단점

• 이미 정렬된 데이터에서는 성능이 떨어질 수 있다.
• 완전 이진 트리 구조를 유지하는 것이 목적이므로, 순회하면서 데이터를 정렬된 순서대로 탐색하는 데는 적합하지 않다.

주요 활용

• 우선 순위 큐
• 힙 정렬

 

힙과 스택의 차이

스택과 힙의 가장 큰 차이점은 메모리 할당과 관리 방법에 있다

 

스택

• 정적 메모리 할당
• 컴파일 시간에 메모리 크기가 결정
• 함수 호출 시 자동으로 메모리가 할당되고 해제

힙

• 동적 메모리 할당
• 프로그램 실행 중에 메모리 크기가 결정
• 개발자가 직접 메모리를 할당하고 해제
• 스택보다 유연하지만 메모리 관리에 더 많은 주의 필요

스택이 속도가 더 빠르고 메모리 관리가 간단하지만 크기에 제한이 있다

힙은 메모리 크기가 유동적이지만, 메모리 누수와 같은 문제를 주의해야한다

 

힙 구현

최소힙에 값 추가

https://github.com/9mans/tree-practice/blob/master/src/heap/MinHeapTest.java

최대힙에서 값 삭제

https://github.com/9mans/tree-practice/blob/master/src/heap/MaxHeapTest.java