알고리즘 힙[Heap]

힙에 대한 기본적인 예시)

Binary Tree - [O(1)]

add : O(log N)

delete: O(log N)

TOP : O(1)

Binary Heap - O(n)

부모 노드가 항상 자식노드보다 커야한다.

삽입하여 값을 변경할 경우 O(log n)

새로운 값을 넣게 되면 부모노드와 비교하고 자리 변동이 일어나기 때문이다.

 

[9, 7, 5, 1, 3]

 

자식 노드에서 부모 노드로 갈 경우 3이 1로 가려는경우 

4 -1 / 2 = 1 (1.5 이지만 내림한다)

index -1 / 2 : to parent

 

부모 노드에서 자식 노드로 갈 경우

2*index + 1 : Lest child

2 * 1   + 1   = 3  (7에서 1로 갈 경우 Index=1  결과값 index3은 1이다)

 

2*index + 2 : Right child

2 * 1  + 2  = 4  (7에서 3으로 갈 경우 공식 대입후 결과값 4가 나타난다. index 4는 3)

 

힙이란?

~자 갑니다~ 힙!

- 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된  "완전 이진 트리"

힙은 최대힙&최소힙 두가지가 있습니다.

최대 힙: 내 자식 노드의 값은 내 값보다 작거나 같아야한다.

최소 힙: 내 자식 노드의 값은 내 값보다 크거나 같아야 한다.

 

BST와 달리 내 왼쪽 자식, 오른쪽 자식 간의 크기는 상관이 없다.

최대 힙의 경우 왼쪽 자식 노드가 커도 되고, 오른쪽이 커도 된다.

대신 자식 노드가 부모노드보다는 항상 작아야 한다.(같아도된다)

 

일반적으로 힙은 배열을 이용해서 구현한다.

BST와 달리 완전 이진 트리이기 때문에, 노드간 index관계를 나타낼 수 있기 때문이다.

 

완전 이진 트리는 무조건 왼쪽 자식 노드부터 차례차례 채워지기 때문에 사용한다.

노드가 생성되는 순서를 index로 표현할 수 있다.

그래서 부모와 자식 간의 index를 서로 구할 수 있다.

 

위 에 표현 되어 있으므로 다시 한번더 자료를 가져 오겠습니다.

 

[9, 7, 5, 1, 3]

 

자식 노드에서 부모 노드로 갈 경우 3이 1로 가려는경우 

4 -1 / 2 = 1 (1.5 이지만 내림한다)

index -1 / 2 : to parent

 

부모 노드에서 자식 노드로 갈 경우

2*index + 1 : Lest child

2 * 1   + 1   = 3  (7에서 1로 갈 경우 Index=1  결과값 index3은 1이다)

 

2*index + 2 : Right child

2 * 1  + 2  = 4  (7에서 3으로 갈 경우 공식 대입후 결과값 4가 나타난다. index 4는 3)

 

이런식을 부모 자식 관계를 인덱스값으로 찾을수 있다.

 

 

힙의 시간 복잡도

힙의 시간은 O(log N)

한번 실행 시마다 50%의 실행을 제거할 수 있다는 의미가 있다.

배열에 데이터를 넣고 최대&최소를 찾으려먼 O(n)이 걸리지만

힙에 넣을 경우 O(log N)으로 좀더 빠르게 찾을 수 있어

우선순위 큐 같이 최대값 & 최소값을 빠르게 찾아야 되는 알고리즘이나 자료구조에  활용됨.