힙

• 형태 속성 : 힙은 완전 이진 트리 (완전 이진 트리의 높이 O(lg(n)))
• 힙 속성 : 모든 노드의 데이터는 자식 노드들의 데이터 보다 크거나 같다.

정렬 알고리즘 : 데이터를 재배치하는 구체적인 방법

 

힙 구현하기

• 완전 이진 트리이기 때문에 동적 배열로 구현 ⇒ 파이썬에서는 동적 배열을 활용한 리스트로 구현

왼쪽 자식 인덱스 : 인덱스 * 2

오른쪽 자식 인덱스 : 인덱스*2+1

 

Heapify

원하는 노드를 힙속성에 맞는 위치로 재배치 시키는 알고리즘

시간 복잡도 O(lg(n))

주어진 리스트를 힙으로 만들기

⇒ 가장 맨마지막 노드부터 루트 노드까지 heapify를 호출해준다.

→ 역순으로 heapify를 호출해주면 부분트리마다 힙속성을 만족시키고 올라가기 때문에 모든 노드를 힙속성에 맞출수있고 힙이 완성된다.

→ 이때 시간 복잡도는 O(nlg(n))

 

힙 정렬

1. 힙을 만든다
2. root 노드와 마지막 노드를 바꿔준다.
3. (바꾼 노드는 없는 노드 취급한다.)
4. 새로운 노드가 힙속성을 지킬 수있게 heapify 호출
5. 2~4과정을 모든 인덱스를 돌 때 까지 반복

⇒ 맨위의 노드가 가장 큰 숫자라는 것을 이용하여 추출하는 방식

 

힙정렬의 시간 복잡도

힙을 만드는데 ⇒ O(nlg(n))

만든 힙에서 매번 root를 뽑고 남은 것들을 다시 힙으로 만들어주는 작업을 반복하는데 ⇒O(nlg(n))

즉, 힙정렬의 시간 복잡도는 O(nlg(n))+ O(nlg(n))= O(2nlg(n))⇒O(nlg(n))

 

정렬 알고리즘	시간 복잡도
선택 정렬	O(n2)
삽입 정렬	O(n2)
합병 정렬	O(nlg(n))
퀵 정렬	평균 O(nlg(n)) 최악 O(n2))
힙 정렬	O(nlg(n))

 

우선순위큐

• 추상 자료형
• 데이터를 저장 할수있다
• 저장한 데이터가 우선 순위 순서대로 나온다.
• 힙을 이용하면 우선 순위 큐를 효울적으로 구현할수있다.

우선순위큐를 구현하기 위해서는 삽입과 삭제 연산을 잘 알아야한다.

힙에 데이터 삽입 하기

• 힙의 마지막 인덱스에 데이터를 삽입 한다.
• 삽입한 데이터와 부모 노드의 데이터를 비교한다
• 부모노드의 데이터가 더작으면 둘의 위치를 바꿔준다.,
• 2번째와 3번째가 힙속성을 만족 할때까지 반복한다.

힙에서 root 노드 데이터 추출하기

• root노드와 마지막 노드를 서로 바꿔 준다.
• 마지막 노드의 데이터를 변수에 저장해준다
• 마지막 노드를 삭제한다
• root 노드에 heapify를 호출해서 망가진 힙속성을 고친다.
• 변수에 저장한 데이터를 리턴한다.(최고 우선 순위데이터)

힙의 삽입 시간 복잡도 : O(lg(n)) ⇒ heapify와 다르지만 역으로 찾아 올라가는 거기 때문에 heapify와 비슷한 시간 복잡도를 지닌다.

힙의 추출 연산시간 복잡도 : O(lg(n)) ⇒ heapifty의 시간 복잡도만 큼 걸린다.

 

정렬된 동적배열에서 우선 순위큐를 구현했을 때 시간 복잡도

삽입 : O(n)

삭제 : O(1)

 

정렬된 더블 링크드 리스트에서 우선 순위큐를 구현했을때 시간 복잡도

삽입 : O(n)

삭제 : O(1)

 

	데이터 삽입	데이터 추출
정렬된 동적 배열	O(n)	O(1)
정렬된 더블리 링크드 리스트	O(n)	O(1)
힙	O(lg(n))	O(lg(n))

 

• 정렬된 동적 배열이나 정렬된 더블 링크드 리스트를 사용하면 데이터를 추출할때 더 효율적
• 힙을 사용하면 데이터를 삽입할때 더 효울적