(최대 힙 얘기만 하겠다. 최소 힙은 그 반대임)
힙은 완전 이진트리의 일종이고, 부모노드가 자식노드보다 크다는 성질을 갖고있다. 완전이진트리가 무엇인지 안다면 어렵지 않은 정의이다. 제일 중요한건 이 자료구조 존재의 목적이다. 이 목적으로부터 heap sort도 파생된다.
목적
힙 자료구조는 최댓값 을 "빨리" 뽑아내기 위해 존재하는 자료구조이다.
예를들어 리스트에서는 최댓값을 뽑아내려면 선형적인 O(N) 의 시간이 걸린다. 데이터가 많아질수록 부담스러운 시간 복잡도이다. 힙은 최악의 경우에도 O(logN) 의 시간 복잡도를 가진다. 완전이진트리 내부에서 수직으로 이동하며 뽑는 구조이기에, 당연히 logN 이겠다. (이진트리 + 수직이면 2의 n승의 반대니까)
그럼 무조건 힙쓰지? 라고 묻는다면, heapify() 과정을 설명해주겠다.
비용
' heapify() '
heapify는 직관적으로 느껴지는 그 뜻이 맞다. 힙 형태로 바뀐다는 뜻이다.
데이터를 자료구조에 넣고 뺄때, Heap의 성질을 유지하게 만들기 위한 작업이자 비용이다. O(logN)이 걸린다.
뭔말이냐면, 최댓값을 언제든지 쉽게 스윽 뽑아갈 수 있도록 적합한 형태로 트리에 데이터들을 잘 배치해 놓겠다는 것이다.
이해
1~10 을 갖고있는 배열을 힙으로 나타낸다면 다음과 같을 것이다.
이 녀석은 완전이진트리이자, 힙이다.
heapify() 1. 삭제
최댓값을 내놓게 된다면,
누군가 최댓값을 내놓으라 한다면 주저없이 최상단레벨의 root 노드인 10을 내어주면 된다. 10이 나가고 나면 트리가 깨지겠지? 이때 나중에 또 최댓값을 내놓으라 할 수 있으니, 다시 힙 형태로 바꿔놓자. heapify() 를 한다는 뜻이다.
10을 삭제한 자리에 마지막 노드 data 인 1을 일단 냅다 때려 넣어버린다. 그럼 이제 아래 자식노드들이 황당할것이다. 굉장히 작고 귀여운 숫자가 root에 앉아있으니말이다.
따라서 최상단에 새로 자리한 노드는 자식노드 2개중 작은녀석과 swap() 을 반복한다.
그러다보면 언젠가 본인보다 큰 자식노드가 없어 자리에 정착하게 될것이다. 그럼 heapify()가 완료된 것이다.
heapify() 2. 삽입
힙에 새로운 데이터가 들어온다면,
자료구조에 새로운 데이터가 들어올 수 있다. 어디다가 넣을 것인가? heap의 성질을 유지하도록, 부모노드가 자식노드보다 큰 데이터를 지니고있도록 해야한다.
고민할것없이 그냥 마지막 노드에 일단 냅다 때려 넣어라.
그럼 그 위에 노드들은 불안할것이다. 자신보다 훨씬 큰 데이터가 자식으로 들어왔으니 말이다.
따라서 신병으로 들어온 데이터는 부모노드와 비교를 해서 본인이 더 크다면 swap()하는 과정을 반복한다.
그러다보면 언젠가 본인이 부모노드보다 작아서 어떤 자리에 정착하게 될 것이다. 그럼 heapify()가 완료된 것이다.
.
.
.
