힙: O(1) 시간에 가장 높은 항목이나 가장 낮은 항목을 반환하는 자료구조
힙에 대한 이해
힙은 트리와 비슷한 자료구조의 일종이다.
최대 힙은 부모 노드가 자식보다 크고, 최소 힙은 부모 노드가 자식보다 작은 것을 이른다.
힙은 자료를 정렬할 때 유용하게 사용한다. 대표적으로 메모리에서 데이터를 동적으로 저장할 때 힙 자료구조가 사용된다.
힙은 (자식에 대한 포인터를 갖는 대신) 배열을 사용해 자료를 저장한다. 배열의 인덱스를 통해 힙 노드의 자식 위치를 쉽게 알 수 있다.
배열의 인덱스는 각 노드의 차수/높이를 정의한다.
힙은 어떤 종류의 값이든 저장할 수 있다.
최대 힙
최대 힙(max-heap): 루트 노드가 가장 높은 값을 갖고 각 노드의 값이 자식의 값보다 크다. (부모가 모든 자식보다 항상 큰 힙)
최소 힙
최소 힙(min-heap): 루트 노드가 가장 낮은 값을 갖고 각 노드의 값이 자식의 값보다 작다. (부모가 모든 자식보다 항상 작은 힙
이진 힙 배열 인덱스 구조
노드 인덱스
(자신) N
부모 (N-1) / 2
왼쪽 자식 (N*2) + 1
오른쪽 자식 (N*2) + 2Percolation
Percolation(삼투): 위로 아래로 이동하는 동작
노드를 추가하거나 삭제할 때 힙의 구조가 유지되어야 한다. 이를 위해 노드 간에 교환이 일어나면서 bubble-up, bubble-down 동작이 이루어진다.
이런 노드 간 전파의 시간 복잡도는 O(log2(n))이다.
최대 힙 구조에서는 제일 위에 최솟값 노드가 위치할 때까지 노드 교환이 이루어지고,
최소 힙 구조에서는 제일 위해 최댓값 노드가 위치할 때까지 노드 교환이 이루어진다.
힙 정렬
힙 정렬: 힙이 빈 상태가 될 때까지 힙에 대해 .pop() 메서드를 호출하면서 꺼낸 객체를 저장한다.
Percolation이 O(log2(n)), 정렬이 n개의 항목을 꺼내기 때문에 힙 정렬은 O(nlog2(n))의 시간 복잡도를 지닌다.
힙 정렬에는 내림차순 정렬(최대 힙)과 오름차순 정렬(최소 힙)이 있다.
요약
힙은 배열을 사용한 트리같은 자료 구조이다. Percolation(삼투)를 통해 동작하며, 노드를 삽입하거나 삭제할 때 (삼투를 통해) 노드를 반복적으로 교환하면서 자신의 구조를 유지한다.
