[DataStructure] Heap 이란?

heap은 우선 순위 큐를 위해 만들어진 자료구조로서
완전이진트리를 기반으로 하고 있다. 

우선 순위 큐는 우선순위를 가진 큐로서 입력 순서에 따라 출력되는 기존의 큐와 다르게
입력 순서가 늦어도 우선순위가 높으면 먼저 출력되는 큐를 의미합니다. 

이 우선 순위 큐는 배열, 리스트 ,heap으로 구현이 가능한데
여기서 heap으로 구현하는것이 제일 효율적이다. 

그 이유는 heap의 삽입,삭제 연산의 시간 복잡도가 모두 log n 이기 때문입니다.

heap은 배열로 구현이 가능합니다. 

heap의 삽입 : 맨마지막에 삽입 후 heap을 만드는 과정 (log n)으로 끝
-> heap 만드는 과정 : 인덱스/2 를 한 값과 비교해가면서 (부모보다 크다, 부모모다 작다 등의 조건 만족할 때 까지 반복) 

heap의 삭제: 루트 노드 삭제 후, 마지막 노드 값을 루트 노드에 입력. 다시 heap을 만드는 과정(log n)으로 끝

max Heap : 부모 노드가 무조건 자식보다 큰것 (root 노트가 최대 값)
min Heap : 부모 노드가 무조건 자식보다 작은 것(root 노트가 최소 값)

왼쪽 자식의 인덱스 = (부모의 인덱스)*2
오른쪽 자식의 인덱스 = (부모의 인덱스)*2 + 1
부모의 인덱스 = (자식의 인덱스)/2

-> 완전이진트리를 배열로 만듦으로써 생기는 규칙

 

-------------------------------------------------------------------------------------------------
배열의 단점
1. 데이터 삽입 및 삭제 과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산이 있다.
2. 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야한다.
-> 이 경우 우선순위가 가장 낮은 데이터 저장하는 경우 n번 조사해야함

순서없는 배열 
삽입 O(1)인 이유, 정렬안하니깐 넣을때 아무데나 넣음
삭제 O(n)인 이유, 우선순위 제일 높은거 뺄 때 선형탐색으로 찾아야함
순서없는 연결리스트
배열과 동일

만약 정렬한 경우
삽입 O(n)인 경우, 정렬된 상태를 유지하기 위해 우선순위를 순차적으로 비교해야함
만약 이진탐색으로 탐색에 log n 번 소요했다고 하더라도,
배열을 한칸씩 미는 과정에서 O(n) 소요

삭제는 맨 뒤에꺼 지우면 끝(맨 앞에껄로 안하는 이유는 지우고, 땡기는 과정이 N번 들기 때문)

연결리스트
마찬가지로 삽입시 순차적으로 비교하면서 위치 탐색에 O(n) 번 걸림
-----------------------------------------------------------------------------------------------------