Heap Sort, 다익스트라 알고리즘

Heap Sort와 다익스트라 알고리즘 정리

정렬 알고리즘과 최단 경로 알고리즘은 알고리즘 학습에서 자주 등장하는 주제다.
이번에는 Heap Sort(힙 정렬) 과 다익스트라 알고리즘을 정리해본다.

1. Heap Sort (힙 정렬)

(1) Heap 이란?

완전 이진 트리 형태를 가지는 자료구조

부모 노드와 자식 노드 간에 힙 속성(Heap Property) 을 만족

최대 힙(Max Heap): 부모 ≥ 자식

최소 힙(Min Heap): 부모 ≤ 자식

(2) Heap Sort 동작 원리

배열을 Max Heap 으로 변환한다. 그 후, Root(최댓값)를 배열 끝으로 보내고, 힙 크기를 줄인다. > 다시 힙을 재정렬(Heapify).

이를 반복하면 오름차순 정렬이 완성된다.

(3) 파이썬 코드

# MAX HEAP
arr=[234,215,24,6325623,56] # 1차원 배열
heap=[0]*len(arr)**2 #arr 길이보다 길어야함
hindex=1

def insert(value): # 완전이진트리
    global hindex
    heap[hindex] = value
    now=hindex
    hindex+=1 # 트리의 마지막 인덱스 +1
    while 1:  # 부모랑 비교 후 필요시 swap
        p=now//2
        if p==0: break
        if heap[p] >= heap[now]: break
        heap[p],heap[now]=heap[now],heap[p]
        now=p # swap후 부모랑 비교(부모가 그 다음 now)

def top(): # 출력
    return heap[1]

def pop(): # 출력 후 tree 재조정하는 함수
    global hindex
    hindex-=1
    heap[1]=heap[hindex]
    heap[hindex]=0
    now=1
    while 1:
        son=now*2 # 왼쪽 자식
        rson=son+1 # 오른쪽 자식
        # 오른쪽 자식 존재 and R자식이 L자식보다 크면 R자식을 부모랑 비교할 자식으로 선택
        if rson<hindex and heap[son] < heap[rson]: son=rson
        # 자식이 아예 없거나 or 부모가 자식보다 크다면  종료
        if son>=hindex or heap[now]>heap[son]: break
        heap[son],heap[now]=heap[now],heap[son]
        now=son # swap후 또 그 밑의 자식이랑 비교 (자식이 다음스테이지에서 부모가되어 그 자식들과 비교)

for i in range(len(arr)):
    insert(arr[i])

for i in range(len(arr)):
    print(top(),end=' ')
    pop()

(4) 시간 복잡도

힙 구성: O(n)

최대 원소 꺼내기 × n번: O(n log n)

전체: O(n log n)

공간 복잡도: 추가 배열 없이 수행 가능 → O(1)

2. 다익스트라 알고리즘 (Dijkstra’s Algorithm)

(1) 문제 정의

그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘.
단, 간선 가중치가 음수가 없어야 한다는 제약이 있다.

(2) 아이디어

거리를 저장하는 배열 dist를 관리한다.

시작점에서 가장 가까운 정점을 하나씩 확정한다.

각 확정된 정점에서 인접한 정점들의 거리를 갱신(Relaxation).

이 과정을 우선순위 큐(Heap)를 이용해 효율적으로 구현.

(3) 파이썬 코드

inf=21e8
arr=[
[0,3,9,inf,5],
[inf,0,inf,7,1],
[inf,inf,0,inf,inf],
[inf,inf,1,0,inf],
[inf,inf,inf,1,0]]

used=[0]*5
result=[inf]*5

# 시작점 0번 인덱스
# 시작점을 첫번째 경유지.
used[0]=1
result[0]=0
def ky():  
# 경유지 선택한 적이 없고 + result배열의 최소값이라면
    Min=21e8
    Min_index=0
    for i in range(5):
        if used[i]==0 and result[i]<Min:
            Min=result[i]
            Min_index=i
    return Min_index

def dijkstra():	#경유지 선택
    for i in range(5):
        via=ky()
        used[via]=1	
        # 시작점~도착점 vs 시작점~경유지~도착지 최소값을 result에 갱신 /갱신 후 j = 다른 모든 정점(도착index).
        for j in range(5): 
            baro=result[j]
            kyung=result[via]+arr[via][j] # 시작->경유지 + 경유지->도착
            if baro > kyung:
                result[j]=kyung

dijkstra()
print(*result)

(4) 시간 복잡도

우선순위 큐 사용 시: O((V + E) log V)

인접 리스트 기반 구현에서 가장 효율적

공간 복잡도: O(V + E)

3. 비교 및 정리

Heap Sort: 정렬 문제 → 힙 구조 기반, O(n log n) 보장

Dijkstra: 최단 경로 문제 → 우선순위 큐 기반, O((V + E) log V)

두 알고리즘 모두 힙(Heap)을 활용한다는 공통점이 있다.
정렬에서는 힙으로 원소를 꺼내는 과정이 핵심이고,
다익스트라에서는 최단 거리를 확정할 정점을 고르는 과정에 힙이 사용된다.