Heap

Heap

Heap이란 완전 이진 트리의 일종으로 부모 노드와 자식 노드간에 항상 대소관계가 성립하는 자료구조를 의미합니다.

부모가 항상 자식보다 큰 힙을 최대힙(MaxHeap)이라 하며,
부모가 자식보다 항상 작은 힙을 최소힙(MinHeap)이라 합니다

여기서 형제 노드들간에는 관계가 없습니다
부모와 자식사이의 관계가 중요합니다

heap의 원소 추가, 삭제의 시간복잡도는 모두 O(logn) 입니다

heap은 배열과 인덱스1개를 사용하여 관리합니다
루트노드는 배열1번에 있습니다
부모노드의 인덱스가 n이라면 자식노드는 2n, 2n+1번 노드입니다.

0부터 시작하지 않는 이유는 부모,자식노드 관리를 편하게 해주기 위해서입니다.
루트노드:0, 부모노드n이면 자식노드: 2n+1,2n+2 이렇게 관리할 수도 있습니다

이 다음부터 heap에 원소의 추가,삭제 과정에 대해 알아보겠습니다

최소힙을 기준으로 설명하겠습니다

push()

heap에 데이터를 추가하는 과정
1. 마지막노드에 데이터를 추가하고 마지막인덱스 번호+1
2. 마지막노드가 그 부모노드보다 값이 작다면 부모노드와 마지막노드의 값을 swap
3. 2번과정을 반복하여 부모노드가 자식노드보다 항상 작게 관리한다.

pop()

1. 루트노드를 제거한다.
2. 마지막노드를 루트노드로 이동시킨다.
3. 루트노드와 자식노드를 비교하면서 가장 작은 값을 부모노드로 이동시킨다.

   자식노드가 없음 -> break
   자식노드가 1개인데 부모노드보다 값이 작다
   -> 자식노드와 부모노드 swap
   자식노드가 2개
   -> 둘중 작은노드를 가지고 부모노드와 비교한다.

4. 3번과정을 반복하여 부모노드가 자식노드보다 항상 작게 관리한다.

우선순위 큐

힙을 이용하는 대표적인 자료구조
힙을 이용하기 때문에, 데이터를 우선순위 큐에 집어넣으면 자동으로 정렬이 된다.
삽입, 삭제의 시간복잡도가 O(logn)이다

모든 데이터를 삽입하고, 모두 삭제한다면 우선순위 큐를 쓰는 의미가 없다(그냥 정렬과 시간복잡도 같음)

모든 데이터 삽입, 삭제 시간복잡도 O(nlogn)
힙 정렬 시간복잡도 O(nlogn)