시작하기 전에
Heap 은 프로그래밍을 배운 사람이라면 많이 들어본 단어일 것이다.
Stack과 Heap, 정적 메모리와 동적 메모리는 malloc 이나 new 를 배웠다면 필수적으로 알아야하는 단어이다. 이론적보다 현실적으로 와닿는 부분은 기본적인 변수, 배열 선언부터 C++에서 소멸자에서 메모리 해제를 시키거나 Java나 C#의 가비지 컬렉션과 연계된 내용이라고 생각하면 된다.
그런데 C#을 복기하며 Heap 을 Class로 구현할 때 이 Heap 과 메모리 Heap 이 연관성이 있을까 궁금해졌다. 자료구조로서 구현하며 한번 알아보려고 한다.
Heap 이란 왜 나오게 되었는가?
List 를 아는가? C#의 List 는 배열 중에서 크기가 제한되지 않은 배열이라고 생각하면 된다. 이 List 는 다음과 같이 경우가 두 가지 있다.
- Unsorted : 정렬되지 않은
- Sorted : 정렬된
그리고 정렬되지 않은 List 와 정렬된 List 는 삽입, 삭제와 같은 연산을 수행할 때 다음과 같은 시간 복잡도를 가지게 된다.
- 정렬되지 않으면 삭제하는데 어려움을 가지고,
-> 삭제할 값까지 찾아가는데 연산을 수행하기 때문 - 정렬되어 있으면 데이터를 삽입하는데 어려움을 가진다.
-> 정렬된 상태여야 하므로 삽입할 위치를 잡아줄 때 연산을 수행한다.
Priority Queue 를 구현할 때 해당되는 두 List 들은 비효율적인 면이 있다. 그러기 때문에 Priority Queue 를 구현할 때 좀 더 효율적인 자료구조이고 완전 이진트리 인 Heap 자료구조가 나오게 되었다.
그렇다면 Heap은 뭐지?
Heap은 다음과 같은 두 속성을 만족해야한다.
- Heap-Order Property
- Complete Binary Tree Property
스터디의 목적
array based complete binary tree 형태로, min, size, add, remove 메소드 구현
스터디는 array based complete binary tree 로 진행하게 되었다.
결론
Heap을 배우는 이유 중엔 다른 Sort 와 비교해서 보는 경우가 많다.
