힙(heap)이란? 우선순위 큐를 위해 만들어진 자료구조이다.
힙은 완전 이진 트리(Complete Binary Tree)의 일종이다.
힙은 반정렬 상태(느슨한 정렬 상태)를 유지한다.
여러 개의 값들 중에서 최댓값 or 최솟값을 빠르게 찾아내도록 해주는 자료구조이다.
힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값 허용 X)
key(부모 노드) >= key(자식 노드)
key(부모 노드) <= key(자식 노드)
사진 출처 : 링크
표준적으로 배열을 이용하여 힙을 구현한다.
힙에 새로운 요소가 들어오면 --> 새로운 요소를 힙의 제일 마지막 노드에 삽입한다.
새로운 노드(요소)를 부모 노드들과 비교한 후 교환을 통해 힙의 성질을 만족시킨다.
아래 그림은 최대 힙(Max Heap)에 새로운 데이터를 삽입하는 경우이다.
사진 출처 : 링크
최소 힙(Min Heap)에 새로운 데이터를 삽입하는 경우에는 기준key(부모 노드) <= key(자식 노드)
만 다르며 로직은 같다!
최대 힙(Max Heap)에서 최댓값은 루트 노드이다. 따라서 루트 노드가 삭제된다.
삭제된 루트 노드에는 힙의 마지막 노드를 가져와 넣는다.
힙의 성질을 만족시키도록 힙을 재구성한다.
아래 그림은 최대 힙(Max Heap)에서 데이터를 삭제하는 경우이다.
사진 출처 : 링크