목록2025/01/28 (1)

Toolofv 님의 블로그

[Python] 힙 정렬(Heap Sort)

힙(Heap) 정렬 알고리즘은 정렬의 용도로 주로 쓰인다고 볼 수는 없는 것 같다. 힙 자료구조는 원소가 들어갈 때 최댓값, 최소값을 꺼내쓰는데 효율적이기 때문에 다익스트라(dijkstra) 알고리즘같은 경우에도 사용된다. 시간복잡도는 $O(n\ log\ n)$이다. 완전이진트리(complete binary tree)다. 파이썬의 경우 heapq 모듈을 사용한다. 힙 자료구조화와 정렬은 좀 다르다.  Siftdown( )의 경우 범위를 받고 부모노드(parent)를 지정한다. 바로 밑의 자식 노드를 child로 지정한 후 오른쪽의 자식 노드와 비교해 큰 값을 최종 child로 정한다. 지정된 부모노드와 자식 노드를 비교하고 자식 노드 값이 크면 바꿔준다.(최대힙의 경우) 그 것을 반복하면 부모노드와 자식..
Algorithm 2025. 1. 28. 01:30
이전 Prev 1 Next 다음