8.4 요약¶
1. 핵심 정리¶
- 힙은 완전 이진 트리이며, 만족하는 조건에 따라 최대 힙과 최소 힙으로 나뉜다. 최대(최소) 힙의 루트 원소는 가장 큰(작은) 값이다.
- 우선순위 큐는 원소를 꺼내는 우선순위가 있는 큐로 정의되며, 보통 힙으로 구현한다.
- 힙의 주요 연산과 시간 복잡도는 원소 삽입 \(O(\log n)\), 루트 원소 꺼내기 \(O(\log n)\), 루트 원소 접근 \(O(1)\) 등이다.
- 완전 이진 트리는 배열로 표현하기에 매우 적합하므로, 힙은 보통 배열에 저장한다.
- 힙 재정렬 연산은 힙의 성질을 유지하는 데 사용하며, 삽입과 꺼내기 연산 모두에서 필요하다.
- \(n\) 개의 원소를 입력받아 힙을 구성하는 시간 복잡도는 \(O(n)\)까지 최적화할 수 있어 매우 효율적이다.
- Top-k는 대표적인 알고리즘 문제다. 힙 자료 구조를 사용하면 \(O(n \log k)\)의 시간 복잡도로 효율적으로 해결할 수 있다.
2. Q & A¶
Q: 자료 구조의 '힙'과 메모리 관리의 '힙'은 같은 개념인가?
두 개념은 서로 다르며, 우연히 이름만 '힙'으로 같을 뿐이다. 컴퓨터 시스템 메모리의 힙은 동적 메모리 할당에 사용되는 영역으로, 프로그램이 실행 중에 데이터를 저장하는 데 사용할 수 있다. 프로그램은 객체나 배열 같은 복잡한 구조를 저장하기 위해 일정량의 힙 메모리를 요청할 수 있다. 데이터가 더 이상 필요하지 않으면 메모리 누수를 막기 위해 해당 메모리를 해제해야 한다. 스택 메모리에 비해 힙 메모리는 관리와 사용에 더 주의해야 하며, 잘못 사용하면 메모리 누수나 유효하지 않은 포인터 등의 문제가 발생할 수 있다.