힙_2

힙을 활용하는 대표적인 2가지 방법

1. 정렬

2. 우선순위 큐를 구현하는 법

우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 많이 사용된다!

---

정렬 알고리즘

데이터를 재배치하는 구체적인 방법을 정렬 알고리즘이라 한다.

삽입 정렬, 선택 정렬, 퀵 정렬, 합병 정렬 + 힙 정렬 등이 있다.

보통 정렬 알고리즘의 경우 O(n logn) 정도만 되도 효율이 좋은 측에 속한다 하니 아래의 시간 복잡도를 서로 비교해보자.

---

힙 정렬

Tree = [None, 14, 8, 12, 5, 4, 10, 6, 2, 1, 3]

위 예시로 힙 정렬 알고리즘의 방법은 아래와 같이 정리 할 수 있다.

1. 힙을 만든다. (이때 최댓값을 구하고 싶으면 max heap을 반대의 경우 min heap을 사용하면 동일한 알고리즘으로 동작 가능)

2. 루트 노드와 가장 마지막 노드의 위치를 바꿔준다.

3. 바뀐 마지막 노드의 위치를 저장은 되어있지만 없는 것과 같이 간주한다. 

4. 바뀐 루트 노드가 힙 속성을 지킬 수 있도록 heapift를 호출하여 위 과정을 계속 반복하면 아래 결과 이미지가 된다.

 

---

힙 정렬의 시간 복잡도

1단계 : 힙을 만든다.

힙_1 포스팅에서 보았듯 한 번의 heapify를 할 때의 시간 복잡도가 O(log(N))이고 노드의 수가 총 N개 이므로

O(N log N)

2단계 : 노드 위치 변경

단순 위치만을 바꿔주므로 O(1)

3단계 : 바뀐 부모 노드를 기준으로 heapify 하여 트리를 힙 조건에 위배하지 않도록 재배치해준다.

heapify의 시간복잡도인 O(lonN)

4단계 : 결국 힙에 남아있는 노드가 없을 때까지 2~ 3단계를 반복

총노드의 개수 N개 이기 때문에 O(N log N)이다.

결국 힙을 만드는 데 O(N log N)이 걸리고 

만든 힙에서 매번 루트 노드를 뽑고 다시 힙으로 만들어주는 데 O(N logN)이 걸려

시간 복잡도는 O(NlogN) + O(NlogN) = O(2 NlogN) ==> O(NlogN)이다.

---

우선순위 큐

큐의 FIFO (선입 선출) 구조에 우선순위라는 것을 더한 개념의 추상 자료형이다.

큐나 스택과 같이 데이터를 저장할 수 있으며 

저장한 데이터를 우선순위(특정 조건) 순서대로 출력할 수 있게 해 준다.

---

힙과 우선순위 큐가 어떤 연관이 있는 걸까

과장을 조금 보태서 힙은 우선순위 큐를 구현하기 위한 자료구조라고도 할 수 있다고 한다.

그만큼, 우선순위 큐를 힙을 이용해 구현하는 것이 대표적인 방법이라고 한다.

 

왜 힙이 대표적인 방법인지 간단하게 설명하자면 제일 효율적이기 때문이다.

보통 우선순위에 데이터를 추출하는 과정은

삭제하는 값을 반환하는 특성을 이용하기 때문에 삭제 = 추출로 말하기도 한다.

결론부터 말하자면, 힙으로 우선순위 큐를 구현하는 것이 제일 효율이 좋다.

더 자세하게는 삽입 연산의 효율이 가장 좋기 때문이다.

아래에서 추가로 알아보겠지만, 힙의 삽입은 O(logN), 삭제는 O(logN)이다.

따라서 삽입이 많이 이루어지지 않는 작업인지 추출이 많이 이루어지는 작업인지

판단하여 알맞은 자료구조를 선택하는 것이 중요하다고 한다.

---

1. 정렬된 동적 배열로 우선순위 큐를 구현할 경우

삭제 연산은 O(1)으로 깔끔하지만, 삽입 연산의 경우 뒤에 인덱스를 모두 미뤄서 저장해 야하기 때문에 최악의 경우 O(N)이다.

---

2. 정렬된 더블리 링크드 리스트로 우선순위 큐를 구현할 경우

head, tail 특성을 통하면 또한 O(1)으로 굉장히 효율적이지만, 삽입 과정에서 배열과 마찬가지로 삽입 위치를 찾아야 하는 접근/탐색 연산이 필수적으로 필요하므로 O(N)이다.

---

힙으로 우선순위 큐 구현하기

힙으로 우선순위 큐를 구현하기 위해서는 힙에서의 데이터 삽입/ 삭제하는 방법을 알아야 구현할 수 있다.

삽입 연산

위 예시로 삽입하는 방법을 간단하게 아래와 같이 정리할 수 있다. (데이터 15를 삽입한다 가정)

1. 힙의 마지막 인덱스에 데이터를 삽입한다.

2. 삽입한 데이터와 그 부모 노드의 데이터를 비교한다.

3. 부모 노드의 데이터가 더 작으면 서로 위치를 바꿔준다.

4. 위 과정을 새로 삽입된 노드가 힙 속성을 만족하는 위치로 이동할 때까지 반복한다.

아래와 같이 15라는 데이터를 삽입하였다면, 힙 속성을 만족하는 위치로 이동하여 데이터가 삽입되어도 힙 속성을 유지시켜야 한다.

---

삭제 연산(데이터 추출)

단순히 추출하는 것이 아닌 우선순위를 적용한 데이터를 추출하는 방법이다.

위의 힙에서 가장 큰 값이라는 우선순위를 세우고 가장 큰의 데이터를 출력해보자. 우선순위는 정하기 나름이다!

삭제 방법을 아래와 같이 정리할 수 있다.

1. 루트 노드와 마지막 노드의 위치를 바꿔준다.

2. 마지막 노드를 특정 변수에 선언한다.

3. 마지막 노드를 힙에서 삭제한다.

4. 루트 노드로 바뀐 노드가 힙 속성을 만족하도록 heapify 함수를 호출해준다.

5. 힙 속성을 만족할 경우 마지막 노드를 저장하고 있는 특정 변수를 리턴한다.

아래와 같이 17이라는 우선순위가 높은 데이터를 저장하였다면 루트 노드를 heapify 하여 힙 속성을 만족하도록 재배치해준다.

---

힙의 시간 복잡도

위에서는 힙 정렬에 대한 시간 복잡도를 확인해보았다.

힙에서는 배열과 링크드 리스트에서와 달리 접근, 탐색 등에 시간 복잡도가 존재하지 않는다.

이유를 생각해보자면 데이터의 순서에 대한 정보가 아닌 계층 정보를 저장하기 때문이 아닐까 한다. 

또한, 힙을 사용하는 이유에 대해 생각해보면 정렬, 우선순위 큐를 사용하기 위함이다. 순서 데이터를 다뤄야 하는 상황이 아니기에 접근/ 탐색과 같은 연산의 필요성이 무의미하다고 생각한다. 접근/탐색이 필요한 연산에서는 힙을 사용하지 않으면 된다. 

---

힙의 삽입 연산 시간 복잡도

1. 힙의 마지막 인덱스에 데이터를 삽입한다.

O(1)

2. 삽입한 데이터와 그 부모 노드의 데이터를 비교한다.

O(1)

3. 부모 노드의 데이터가 더 작으면 서로 위치를 바꿔준다.

O(1)

4. 위 과정을 새로 삽입된 노드가 힙 속성을 만족하는 위치로 이동할 때까지 반복한다.

최악의 경우는 삽입한 데이터가 루트 노드까지 올라가는 경우인데 이 경우 힙의 높이만큼 2 ~ 3단계를 진행해야 한다 (2~3단계를 하나의 단계로 생각해도 좋다.)

힙의 높이는 O(logN)에 하므로 O(logN)

총 시간 복잡도는 O(logN)

---

힙의 삭제 연산 시간 복잡도

1. 루트 노드와 마지막 노드의 위치를 바꿔준다.

O(1)

2. 마지막 노드를 특정 변수에 선언한다.

O(1)

3. 마지막 노드를 힙에서 삭제한다.

파이썬 리스트 자료구조를 사용하였으며, 파이썬의 리스트 자료구조의 부모는 동적 배열이기 때문이다.

동적 배열에서의 삭제 연산은 O(1)

4. 루트 노드로 바뀐 노드가 힙 속성을 만족하도록 heapify 함수를 호출해준다.

heapify의 시간 복잡도는 O(logN)

5. 힙 속성을 만족할 경우 마지막 노드를 저장하고 있는 특정 변수를 리턴한다.

O(1)

총 시간 복잡도는 O(logN)이다.

 

 

 

출처 : 코드 잇(자료구조)

자료 구조 | 코드잇 (codeit.kr)