백만 년 만에 쓰는 포스팅 의무의 시간이 점점 다가온다... 이상하거나 모르는 게 있다면, 댓글로 질문좀 해주세요... ## 2021년 3월 18일 최종 수정 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ https://youtu.be/_bkow6IykGM 드디어 힙정렬이다.
우리는 앞서 삽입 정렬(InsertionSort)와 병합 정렬(MergeSort)를 공부했다. 시간 복잡도가 좋지 못한 삽입 정렬, 추가적인 메모리가 필요한 병합 정렬 힙정렬을 통해 이 두 문제점을 해결할 수 있다.
삽입 정렬 병합 정렬 힙정렬 worst case의 시간 복잡도 O(n^2) O(nlgn) O(nlgn) in-place sort YES! NO YES!!!
힙(Heap) 자료구조 우선 힙이라는 자료구조에 대해 공부할 필요가 있다. Heap은 '아무렇게나 쌓여 있는 더미'라는 뜻인데, 딱히 관련있어보이진 않는다..
(참고로 컴퓨터 구조에서 배울 힙메모리영역과는 다른 내용이다. 우리가 알고 있는 HIP과도 무관하다.....
#
include
#
알고리즘
#
우선순위큐
#
자료구조
#
자세한
#
힙
#
힙정렬
원문 링크 : 힙정렬(HeapSort)
