프로그래머스 문제를 풀며 Heap 유형의 문제를 풀어보았고 heapq 모듈을 알게 됐다. 문제를 푸는 것에 그치는 것이 아니라, 더 명확히 Heap sort와 heapq 모듈을 더 자세히 알고 싶어 나동빈님 블로그과 daleseo 블로그를 를 참고해 해당 포스팅을 작성했다. 🤗
1. 힙 정렬 (Heap Sort)
힙 정렬은 병합정렬과 퀵 정렬만큼 빠른 알고리즘으로, 실제 고급 프로그래밍 기법으로 갈수록 힙의 개념이 자주 등장하기 때문에 반드시 알고 넘어가야 할 알고리즘이다.
힙 정렬은 힙 트리 구조(Heap Tree Structure)를 이용하는 정렬방법으로, 정렬의 기초 아이디어는 다음과 같다.
💡 힙을 이용해 데이터를 정렬하면 어떨까?
힙 정렬의 예시 ( 출처 : 위키백과 )
2. 이진트리 (Binary Tree)
따라서, 가장 먼저 Heap이 무엇인지 알아야 하며, 힙을 알기 전 이진트리 (Binary Tree)에 대해 알고 있어야 한다.
💡 이진트리 : 모든 노드의 자식 노드가 2개 이하인 트리구조
이진트리는 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드(Node)에 담은 뒤, 노드를 두 개씩 이어 붙이는 구조를 말한다. 이 때, 트리 구조에 맞게 부모 노드에서 자식 노드로 가지가 뻗히며, 이진트리는 모든 노드의 자식 노드가 2개 이하인 노드이다.
흔히, 위와 같은 구조를 이진트리라고 하며, 여기서 트리(Tree)는 그대로 가지를 뻗어나가는 것처럼 데이터가 서로 연결 돼 있다. 트리는 그 형태에 따라 종류가 다양하다.
3. 완전 이진 트리 (Complete Binary Tree)
다음으로, 완전 이진 트리 (Complete Binary Tree)에 대해 알아보자.
💡완전 이진 트리 : 데이터가 루트 노드부터 시작해 왼쪽 자식노드, 오른쪽 자식노드와 같이 자식노드가 차근차근 들어가는 구조의 이진트리
즉, 완전 이진트리는 이진 트리의 노드가 중간에 비어있지 않고, 빽빽히 가득 찬 구조로, 데이터가 1부터 7까지 총 7개를 트리에 삽입하면 다음과 같은 순서로 들어가며, 항상 왼쪽 자식 노드부터 들어간다.
4. Heap
다음으로 힙(Heap)에 대해 알아보자.
💡
Heap:최솟값이나최댓값을 빠르게 찾아내기 위해 완전 이진 트리 기반으로 하는 트리
힙에는 최대 힙과 최소 힙이 존재하는데, 최대 힙은 '부모노드'가 자식노드보다 큰 힙이라고 볼 수 있으며, 일단 힙 정렬을 하기 위해 정해진 데이터를 힙 구조를 가지도록 만들어야 한다.
힙이 어떻게 생겼는지 알기 위해, 힙의 예제들을 살펴보자.
최대 힙은 부모노드의 값이 자식노드보다 커야하며, 아래와 같은 예시가 전부 최대 힙이라고 볼 수 있다.
다만, 트리 안에서 특정 노드 때문에 최대 힙이 붕괴되는 경우가 있다.
아래와 같이 전체로 보면 중간에 있는 데이터 5를 가지는 노드 때문에 최대 힙이 아니지만, 그 위를 봤을 때 최대 힙이 형성되고, 아래쪽을 봤을 때 최대 힙이 형성되지 않는 경우가 만들어질 수 있다.
5. 힙 생성 알고리즘 (Heapify Algorithm)
힙 정렬을 수행하기 위해서, 힙 생성 알고리즘 (Heapify Algorithm)을 사용한다.
힙 생성 알고리즘은 특정한 하나의 노드에 대해 수행하며, 또한, 해당 하나의 노드를 제외하고는 최대 힙이 구성 돼 있는 상태라고 가정한다는 특징이 있다.
위 그림이 그 특징에 해당하며, 위 트리에서 5만 최대 힙 정렬을 수행해주면 전체 트리가 최대 힙 구조로 형성되는 상태이다.
💡힙 생성 알고리즘 : 특정 노드의 두 자식 중, 더 큰 자식과 자신의 위치를 바꾸는 알고리즘
또한, 위치를 바꾼 뒤에도 여전히 자식이 존재하는 경우, 자식 중에서 더 큰 자식과 자신의 위치를 바꿔야하며 이는 자식이 더이상 존재하지 않을 때까지 반복한다. 즉, 위 예시는 5의 두 자식인 7과 4 중 더 큰 자식인 7과 5의 위치를 바꿔주면 되며, 결과는 아래와 같다.
위와 같이 힙 생성 알고리즘은 전체 트리 구조를 가지도록 만든다는 점에서 굉장히 중요한 알고리즘이다.
이러한 힙 생성 알고리즘의 시간복잡도는 한 번 자식 노드로 내려갈 때마다 노드의 개수가 2배씩 증가한다는 점에서 O (log N)이다.
예를 들어, 데이터의 개수가 1024개라면, 대략 10번 정도만 내려가도 된다는 것이다.
💡 다음의 데이터를 오름차순 정렬해보자
7 6 5 8 3 5 9 1 6
기본적으로 완전 이진 트리를 표현하는 가장 쉬운 방법은 배열에 그대로 삽입하는 것으로, 현재 정렬할 데이터의 개수가 9개이기 때문에, 인덱스는 0~8까지 차례대로 담아주게 된다.
즉, 완전 이진 트리에 삽입되는 순서대로 인덱스를 붙여주며, 위 배열을 완전 이진 트리 형태로 출력하면 다음과 같다.
말 그대로, 배열에 있는 인덱스가 그대로 트리로 표현된 것이며 배열을 다시 완전 이진 트리로 표현할 수 있어야 한다. 위 같은 상황에서 모든 원소를 기준으로 힙 생성 알고리즘을 적용해 전체 트리를 힙 구조로 만들면 된다.
이 때, 데이터의 개수가 N개 이므로, 전체 트리를 힙 구조로 만드는 복잡도는 O (N log(N))이다.
따라서, 결과적으로 위와 같이 최대 힙이 구성되며, 이는 O(N log(N))으로 위와 같이 만들 수 있다. 이제부터 실제로 원하는 정렬을 직관적으로 수행 가능하며, 루트에 있는 값을 가장 뒤쪽으로 보내주며 힙 트리의 크기를 1씩 빼준다.
즉, 위처럼 9와 6을 바꾼 후, 9는 정렬이 완료된 것으로 빨간색으로 처리한다. 이제 9를 제외하고 나머지 8개 원소를 기준으로 힙 생성 알고리즘 (Heapify)를 수행하면, 다음과 같다.
이제 다시 가장 큰 숫자인 8이 루트에 존재하며, 이것을 가장 뒤쪽의 원소와 교환한다.
그럼 위처럼 8과 9가 가장 뒤에 배열되어 정렬이 이뤄지며, 이제 이 과정을 반복하면 된다.
6. 힙 정렬의 전체 시간 복잡도 : O (N * log(N))
힙 생성 알고리즘의 시간복잡도는 O (log N)이고 전체 데이터의 개수가 N개이므로, 시간복잡도는 O (N * log(N))이라고 할 수 있다. 또한, 처음 힙 구조를 만드는 복잡도는 O (N * log(N))이었으므로, 전체 힙 정렬의 전체 시간 복잡도는 O(N * log(N)) 이다.
💡힙 정렬의 전체 시간 복잡도 : O (N * log(N))
힙 정렬은 병합정렬과 다르게 별도로 추가적 배열이 필요하지 않는다는 점에서, 메모리 측면에서 몹시 효율적이다. 또한 항상 O(N * log(N))을 보장할 수 있다는 점이 강력한 정렬 알고리즘이며, 이론적으로 퀵 정렬, 병합 정렬보다 더 우위에 있다고 볼 수 있다. 하지만, 단순 속도를 통해 비교하면 퀵 정렬이 평균적으로 더 빠르기 때문에 힙 정렬이 일반적으로 많이 사용되지는 않는다.
힙 생성 함수(heapify)는 최대 힙을 활용한 오름차순 정렬에서 특정 노드를 기준으로 위쪽으로 올라가는 상향식 구현방식과 하향식 구현방식이 있다. 두 방식 모두 시간 복잡도는 동일하다.
위 본문은 상향식 구현방식을 보여준 것이다.
7. Heapq 모듈
heapq 모듈은 이진 트리 (binary tree) 기반의 최소 힙(min heap) 자료구조를 제공한다.
min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은값은 언제나 인덱스 0, 즉, 이진 트리의 루트에 위치한다. 내부적으로 min heap 내의 모든 원소(k)는 항상 자식 원소들(2k+1, 2k+2) 보다 크기가 작거나 같도록 원소가 추가되고 삭제된다.
예를 들어, 아래 그림은 위 공식을 만족시키는 간단한 min heap의 구조를 보여주고 있다.
1 → root / \ 3 5 / \ / 4 8 7
7-1. 모듈 임포트
우선 heapq 모듈은 내장 모듈이기 때문에 파이썬만 설치되어 있으면 다음과 같이 간단하게 임포트 후에 힙 관련 함수를 사용할 수 있다.
import heapq
7-2. 최소 힙 생성
heapq 모듈에은 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와준다. 자바의 PriorityQueue 클래스처럼 리스트와 별개의 자료구조가 아닌 점에 유의해야 한다.
그렇게 때문에, 그냥 빈 리스트를 생성해놓은 다음 heapq 모듈의 함수를 호출할 때 마다 이 리스트를 인자로 넘겨야 한다. 다시말해, 파이썬에서는 heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙이다.
heap = []
7-2. 힙에 원소 추가 : heappush()
heapq 모듈의 heappush() 함수를 이용하여 힙에 원소를 추가할 수 있다. 첫번째 인자는 원소를 추가할 대상 리스트이며 두번째 인자는 추가할 원소를 넘긴다.
heapq.heappush(heap, 4) heapq.heappush(heap, 1) heapq.heappush(heap, 7) heapq.heappush(heap, 3) print(heap) [1, 3, 7, 4]
가장 작은 1이 인덱스 0에 위치하며, 인덱스 1(= k)에 위치한 3은 인덱스 3(= 2k + 1)에 위치한 4보다 크므로 힙의 공식을 만족한다. 내부적으로 이진 트리에 원소를 추가하는 heappush() 함수는 O (log N)의 시간 복잡도를 가진다.
7-3. 힙에서 원소 삭제 : heappop()
heapq 모듈의 heappop() 함수를 이용하여 힙에서 원소를 삭제할 수 있다. 원소를 삭제할 대상 리스트를 인자로 넘기면, 가장 작은 원소를 삭제 후에 그 값을 리턴한다.
print(heapq.heappop(heap)) print(heap) 1 [3, 4, 7]
가장 작았던 1이 삭제되어 리턴되었고, 그 다음으로 작었던 3이 인덱스 0으로 올라왔다.
print(heapq.heappop(heap)) print(heap) 3 [4, 7]
가장 작었던 3이 삭제되어 리턴되었고, 그 다음으로 작았던 4가 인덱스 0으로 올라왔다. 내부적으로 이진 트리로 부터 원소를 삭제하는 heappop() 함수도 역시 O (log N)의 시간 복잡도를 가진다.
7-4. 최소값 삭제하지 않고 얻기 : heap[0]
힙에서 최소값을 삭제하지 않고 단순히 읽기만 하려면 일반적으로 리스트의 첫번째 원소에 접근하듯이 인덱스를 통해 접근하면 된다.
print(heap[0]) 4
여기서 주의사항은 인덱스 0에 가장 작은 원소가 있다고 해서, 인덱스 1에 두번째 작은 원소, 인덱스 2에 세번째 작은 원소가 있다는 보장은 없다는 것이다. 왜냐하면 힙은 heappop() 함수를 호출하여 원소를 삭제할 때마다 이진 트리의 재배치를 통해 매번 새로운 최소값을 인덱스 0에 위치시키기 때문이다.
따라서 두번째로 작은 원소를 얻으려면 바로 heap[1]으로 접근하면 안되고, 반드시 heappop()을 통해 가장 작은 원소를 삭제 후에 heap[0]를 통해 새로운 최소값에 접근해야 한다.
7-5. 기존 리스트를 힙으로 변환 : heapify()
이미 원소가 들어있는 리스트 힙으로 만들려면 heapq 모듈의 heapify()라는 함수에 사용하면 된다.
heap = [4, 1, 7, 3, 8, 5] heapq.heapify(heap) print(heap) [1, 3, 5, 4, 8, 7]
heapify() 함수에 리스트를 인자로 넘기면 리스트 내부의 원소들의 위에서 다룬 힙 구조에 맞게 재배치되며 최소값이 0번째 인덱스에 위치된다. 즉, 비어있는 리스트를 생성한 후 heappush() 함수로 원소를 하나씩 추가한 효과가 난다. heapify() 함수의 성능은 인자로 넘기는 리스트의 원소수에 비례한다. 즉 O(N)의 시간 복잡도를 가진다.
7-6. [응용] 최대 힙
heapq 모듈은 최소 힙(min heap)을 기능만을 동작하기 때문에 최대 힙(max heap)으로 활용하려면 약간의 요령이 필요하다. 바로 힙에 튜플(tuple)를 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용하는 것이다.
따라서, 최대 힙을 만들려면 각 값에 대한 우선 순위를 구한 후, (우선 순위, 값) 구조의 튜플(tuple)을 힙에 추가하거나, 삭제하면 된다. 그리고 힙에서 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값을 취하면 된다. (우선 순위에는 관심이 없으므로 )
import heapq def heap_sort(nums): heap = [] for num in nums: heapq.heappush(heap, num) sorted_nums = [] while heap: sorted_nums.append(heapq.heappop(heap)) return sorted_nums print(heap_sort([4, 1, 7, 3, 8, 5]))
